Computational Complexity Classes

최근 https://github.com/koosaga/project-hardness 의 스터디에 참여하고 있다. 해당 스터디에서 공부한 내용을 아주 간략히 (주로 informal 하다.) 간혹 정리해볼 예정.

P와 NP

P와 FP

• $\mathbb{P}$는 다항 시간(입력 $x$의 크기에 대해 다항식 scale로 bound 됨을 의미)에 풀리는 문제들의 class이다.
  • 유의 사항: 정수 $n$은 $\log_2 n$ 개의 비트로 표현할 수 있으므로 $n$을 입력으로 줄 때 입력의 크기는 $\log_2 n$ 이다. (흔히들 Subset Sum 등을 $\mathbb{P}$라 생각하면서 하는 오해...)
• $\mathbb{FP}$는 다항 시간에 계산 가능한 함수들의 class이다.

어떤 계산 모델을 가정할 것인가?

• 계산 이론에서 사용되는 standard model은 tape, head, state, action table로 구성된 Turing machine
• 우리에게 익숙한 model은 Word-RAM model로 상수 시간에 동작하는 fixed-size bit/arithmetic operations와 random access로 구성
• 그 외 여러 model들이 있을텐데...
• 다행히 위의 모든 model에서 poly-time algorithm의 존재 여부는 동등함

Church-Turing Thesis

• Church-Turing Thesis
  • Everything computable is computable in TMs
• Extended Church-Turing Thesis
  • Everything poly-time computable is in $\mathbb{P}$

Reduction

• 함수 $f$가 (결정) 문제 $A$ 부터 $B$ 로의 reduction 임은 $x \in A \iff f(x) \in B$ 로 정의
• $f \in \mathbb{FP}$ 일 때 특별히 poly-time reduction 으로 부르고, 이러함 $f$가 존재하면 $A \le_p B$ 로 표기
  • $A$에서 $B$로의 poly-time reduction이 존재하면 $B$가 최소한 $A$ 이상으로 어렵다고 (informally) 생각할 수 있음
  • $\le_p$는 transitive

NP

• NP(nondertimistic polynomial time) class는 다음의 두 가지 정의가 있음:
  • Non-deterministic TM으로 poly-time에 해결할 수 있는 문제들의 class
    • NTM = TM with multiple states
  • poly-time에 (맞았음을) 검증 가능한 문제들의 class
• 두 정의가 동치임은 증명 가능함
• 구체적으로는, $A \in \mathbb{NP} \iff \exists B, A={x : \exists^p y, (x, y) \in B}$
  • 여기에서 $\exists^p y$ 는 poly size의 입력 $y$가 존재하는 것을 의미, 이러한 $y$를 witness 또는 certificate라고 부름
• 예시: 4색 문제, SAT, vertex cover, hamiltonian cycle, FACTORING ...

co-NP

• co-NP class는 NP class의 dual로 poly-time에 틀렸음을 검증 가능한 문제들의 class
• $A \in co-\mathbb{NP} \iff \exists B, A = {x : \forall^p y, (x, y) \in B}$
• 예시: FACTORING (이건 $\mathbb{NP} \cap co-\mathbb{NP}$에 속함)

NP-completeness & NP-hardness

• $A \in \mathbb{NP}-hard \iff \forall B \in \mathbb{NP}, B \leq_p A$
• $\mathbb{NP}-complete = \mathbb{NP} \cap \mathbb{NP}-hard$

Facts & Common Beliefs

• $\mathbb{P} \subseteq \mathbb{NP}$ (fact)
• $\mathbb{P} \subseteq co-\mathbb{NP}$ (fact)
• $\mathbb{P} \subsetneq \mathbb{NP}$ (belief)
• $\mathbb{P} \subsetneq co-\mathbb{NP}$ (belief)
• $\mathbb{NP} \neq co-\mathbb{NP}$ (belief)

Randomized Complexity Classes

RP, ZPP, BPP

• $A$가 $\mathbb{RP}$에 속함은 $x \mapsto {yes, no}$ 인 poly-time algorithm $M$이 존재해서
  • $\Pr[M(x)=yes : x \in A] \ge {1 \over 2}$
  • $\Pr[M(x) = no : x \not \in A] = 1$
  으로 정의
• $co-\mathbb{RP}$ 또한 비슷하게 정의
• $A$가 $\mathbb{ZPP}$에 속함은 $x \mapsto {yes, no, idk}$ 인 poly-time algorithm $M$이 존재해서
  • $\Pr[M(x) = idk] \le {1 \over 2}$
  • $M$의 출력이 yes, no 인 경우 올바름
  으로 정의
• $A$가 $\mathbb{BPP}$에 속함은 $x \mapsto {yes, no}$ 인 poly-time algorithm $M$이 존재해서
  • $\Pr[M(x) = yes : x \in A] \ge {3 \over 4}$
  • $\Pr[M(x) = no : x \not \in A] \ge {3 \over 4}$
  으로 정의

Facts & Common Beliefs

• Fact: $\mathbb{ZPP} = \mathbb{RP} \cap co-\mathbb{RP}$
• Common Belief: $\mathbb{P} = \mathbb{ZPP} = \mathbb{RP}$

Higher Complexity Classes

• $\mathbb{EXPTIME}$: $2^{n ^{O(1)}}$ 시간에 solvable
• $\mathbb{PSPACE}$: $n^{O(1)}$ 메모리로 solvable
• $\mathbb{NPSPACE}$: $\mathbb{PSPACE}$로 검증 가능
• $\mathbb{EXPSPACE}$: $2^{n^{O(1)}}$ 메모리로 solvable

Facts

• $\mathbb{P} \neq \mathbb{EXPTIME}$
• $\mathbb{PSPACE} \neq \mathbb{EXPSPACE}$
• $\mathbb{NP} \subseteq \mathbb{PSPACE} \subseteq \mathbb{EXPTIME}$

Exercise

실제 강의 자료와 넘버링이 상이함에 유의하라.

 

Exercise 1. SAT $\le_p$ Zero-One Integer Program임을 보여라.

 

(Poly-time) Reduction을 하나 구상해보자.

변수 $x_1, x_2, \cdots, x_n$와 클로져 $C_1, C_2, \cdots, C_m$ 으로 구성된 SAT 인스턴스가 있다고 하자. Binary 변수 $y_1, y_2, \cdots, y_n$을 도입하여 $f(x_i) = y_i$, $f(\bar x_i) = 1 - y_i$로 매핑해주자. 이제, 클로져 $C_i = (l_1 \lor l_2 \lor \cdots \lor l_k)$에 대해 $g(C_i) = f(l_1) + f(l_2) + \cdots + f(l_k)$ 로 매핑해줄 수 있다. 그러면, 주어진 instance가 SAT에 속함과 $i = 1, 2, \cdots, m$에 대해 $g(C_i) \ge 1$을 만족시키는 $y_1, y_2, \cdots, y_n$이 존재함이 동치가 된다.

 

Exercise 2. PRIMES에 대한 polynomial size witness를 찾아라.

1. $\mathbb{Z}_p^*$의 원소 가운데 $x^n = 1$을 만족하는 것은 $n$개 이하이다.
   • $\mathbb{Z}_p[x]$는 unique factorization domain 이므로 명백하다.
2. $\mathbb{Z}_p^*$은 cyclic group이다.
   • $A(d)$를 order가 정확히 $d$인 $x \in \mathbb{Z}_p^*$ 들의 집합이라 하자.
   • $|A(d)| \in {0, \phi(d)}$
     • $x \in A(d)$가 존재한다고 하자.
     • 그러면 $|\left<x\right>| = d$ 이므로, $\left< x \right> = {y \in \mathbb{Z}_p^* : y^d = 1}$이 된다.
     • 이 경우, $A(d)$가 $\left< x \right>$의 generator의 집합과 같으므로, 총 $|A(d)| = \phi(d)$.
   • $p = \sum_{d | p} |A(d)| \le \sum_{d | p} \phi(d) = p$ 이므로, $|A(d)| = \phi(d)$ for all $d | p$.
   • 따라서, $|A(p)| = \phi(p) > 0$.
3. Multiplicative group $G$에 대해 $g \in G$가 모든 $q | m (=|G|)$인 소수 $q$에 대해 $g^{m/q} \neq 1$ 을 만족함과 $g$가 generator임은 동치이다.
   • ($\Leftarrow$) : 명백하다.
   • ($\Rightarrow$) : $g^k = 1$ 을 만족한다면, $k | m$ 이므로 명백.
4. 이 사실을 이용하면 소수 $p$에 대한 witness를 $p-1$의 소인수를 이용해 귀납적으로 정의해줄 수 있다.