NP and Computational Intractability

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

NP (Nondeterministic Polynomial-time)

Decision problem

X는 set of strings, 

$X : A(s) =$ yes / no $iff \in X$

X는 dicision problem이고, A는 decision problem을 푸는 알고리즘이다.

즉, input이 들어갔을 때, yes/no로 답하는 문제를 decision problem이라 한다.

대표적으로 어떤 숫자가 소수인지 아닌지를 검사하는 문제가 있다.

 

 

Polynomial time

모든 s에 대해 알고리즘을 돌렸을 때, input size에 대해 polynomial 시간에 돌아갈 수 있으면, 이 알고리즘은 polynomial-time에 실행된다고 한다.

 

 

Certifier

algorithm C(s, t) :  problem X안의 모든 string s에 대해, $C(s, t) =$ yes / no를 출력할 수 있는 t가 존재하면 C를 certifier라 한다. 즉, t는 deicision problem을 푸는데 어떠한 무언가라고 생각하면 된다.

 

 

NP

Decision problem에서 poly-time인 certifier가 존재하면 NP 문제이다.

 

 

예를 들어, CNF가 true/false인지 알아내는 문제에서는

 

 

 

s와 t를 다음과 같이 설정하고 poly-time에 이것이 참인지 거짓인지 알 수 있기 때문에 NP 문제이다.

 

Hamiltonian cycle은 모든 노드를 하나의 cycle로 표현하는 문제이다. 아래 그림처럼 t가 주어졌을 때, hamiltonian cycle임을 확인하는 과정은 poly-time이므로 NP 문제이다.

 

 

 

 

 

P, NP, EXP

EXP는 decision problem을 exponential time에 풀수있는 problem이다.

 

1. $P \subseteq NP$

X를 P라하면 poly-time algorithmdls A(s)가 존재한다. Certifier를 C(s, t) = A(s)로 두고 t를 empty값으로 두어도 certifer가 poly-time이므로 성립한다.

 

2. $NP \subseteq EXP$

NP X에 대한 certifier C(s, t)일 때, t에 모든 것을 모두 넣어보자. 모두 실행했다 했을 때, yes/no 값을 알아 낼 수 있다. 이 때, 가능한 t의 조합은 exponential number이므로 성립한다.

 

 

 

NP - Completeness

Polynomial transforms

Problem X를 변형시켜 problem Y로 만들어 yes/no 여부를 알 수 있다면, X는 Y로 polynomial transform 하였다고 한다.

 

NP-complete

다음을 만족하면 problem Y는 NP complete이다.

1. Y가 NP이다.

2. NP에 속하는 모든 problem X에 대해 Y로 transform 가능함을 보인다. ($X \le_P Y$임을 보임)

 

Theorem

Y가 NP-complete problem이라 하자. Y is solvable in poly-time iff P=NP

 

Pf )

1. $\Leftarrow$

P = NP이므로 P 정의에 의해 poly-time에 풀 수 있다.

 

2. $\Rightarrow$

$X \in NP$인 어떠한 X를 잡아도 $X \le_P Y$가 성립하므로, $NP \subseteq P$이다. 

그리고 위에서 증명했듯이 $P \subseteq NP$이므로 $P = NP$

 

 

Theorem

CIRCUIT-SAT is NP-complete

 

 

위의 그림처럼 논리식이 주어졌을 때, hard-coded input (binary input)이 주어졌을 때, output을 true로 만드는 input이 있는지 확인하는 문제를 Circuit Satisfiability 문제라 한다.

 

Pf )

1. 위의 그림처럼 특정한 input (certificate)를 잡으면 poly-time에 확인가능하므로 NP 문제이다.

2. 어떤 알고리즘이 poly-time이라면 이를 구현하는 circuit 또한 poly-size가 된다. NP의 어떤 문제 X가 있다고 하자. NP의 정의에 따라 X내의 instance s와 그의 certificate t가 존재한다. 이것이 만족하는지 확인하는 과정은 poly-time이므로 circuit또한 poly-size가 되기 때문에 $X \le_P Y$가 성립한다.

 

 

예를들어, INDEPENDENT SET 문제는 아래의 그래프 CIRCUIT-SAT으로 변환할 수 있다.

 

 

 

 

 

Establishing NP-Completeness

이제, 몇개의 NP-Completeness 문제를 알고 있으므로 이를 이용해서 어떤 문제 Y가 NP-Completeness인지 확인하는 것은 다음 과정으로 확인할 수 있다.

 

1. Y가 NP임을 보임

2. NP-Compltet 문제 X를 고름

3. $X \le_P Y$임을 보인다.

 

Pf )

NP 상의 어떤 문제 W가 있다 하자. 그러면 다음 식이 성립한다.

 

$W \le_P X \le_P Y$

 

transitivity로 인해 어떤 W에 대해 $W \le_P Y$가 성립하므로 Y는 NP-complete이다.

 

 

Theorem

3-SAT is NP-complete

 

Pf )

3-SAT은 certifier가 존재하므로 NP 문제이다.

Circuit 논리식은 각각 clause 논리식으로 변환가능하다. (어떻게 변환하는지는 생략)

그리고 모든 clause의 length를 3으로 맞춰준다.

따라서 CIRCUIT-SAT은 3-SAT으로 변환가능하여 풀 수 있다. $CIRCUIT-SAT \le_P 3-SAT$

3-SAT는 NP-complete이다.

 

 

이런식으로 문제간 transform을 이용해 NP-complete를 증명할 수 있고, 다음 그림과 같은 관계가 성립한다.