NP-Completeness ( P, NP, EXP, NP-completeness )

P 란? 

Polynomial time 이내에 해결 가능한 알고리즘을 말한다. 즉, 알고리즘의 복잡도가 O(n^x)로 표현되는 모든 문제들을 말한다. 이때, 해결 이란 단어에 대해 자세히 말하고 싶은데, 여기서 말하는 해결이란 어떠한 instance에 대해 동일하게 해답을 내놓을 수 있는 방법을 말한다.

 

 

 

Certifiers

 

NP

Polynomial time에 답의 존재유무를 확인 할 수 있는 문제를 말한다. NP는 non-deterministic polynomial time의 약자 NP에 속하는 문제들이 다항시간에 해결 가능한지, 불가능한지 모르기 때문이다. 마찬가지로 답을 확인한다는 것에 대해 말하고 싶은데 흔히 결정문제라고도 말한다. 해결 방법은 모르지만 답의 유무는 확인 가능한 문제들의 집합이다.

P 는 NP에 속해있지만 P = NP인지는 아무도 모름

 

Exponential Time (EXP)

Exponential Time (EXP) 는 input s 에 대해 O(2poly(|s|)) 시간 안에 해결 가능한 모든 문제들의 집합이다.

실제로 가장 어려운 분류의 문제들

 

co-NP (NP의 부류)

 

가장 어려운 문제가 되려면…?

-NP 에 속해 있어야 한다.

-최소한 NP 에 속한 다른 모든 문제들 보다는 어려워야 한다.

두 problem 들 간에 난이도를 비교할 수 있는 방법으로 reduction 이 있었다

 

Def) Problem X 가 다음과 같은 조건들을 만족하면 NP-complete 라 한다.

조건 1 : X ∈ NP

조건 2 (Hardness) : 어떠한 Y ∈ NP 에 대해서도 Y ≤p X가 성립

 

Def) Problem X 가 다음과 같은 조건을 만족하면 NP-hard 라 한다.

조건 1 (Hardness) : 어떠한 Y ∈ NP 에 대해서도 Y ≤p X 가 성립.

 

 -NP-hard problem 은 NP-complete problem 을 포함하고 있다.

 -예를 들어 Halting problem (정지문제) 는 NP-hard problem 이지만 NP-complete 는 아니다.

 

NP-Completeness

문제 A가 NP에 속하며,

동시에 NP에 속하는 모든 문제에 대해 polynomial-time many-one reducible되는 문제들의 집합이다.

 

-앞 proposition 에 의해 NP-complete problem X 를 polynomial time 안에 해결하는 algorithm 이 존재한다면, P=NP 임을 알 수 있다.

 

대부분의 사람들은 현재 P ≠ NP 라 생각하고 있으며, 따라서 X 를 해결하는 polynomial-time algorithm 또한 없을 거라 생각하고 있다.

 

Np - complete 증명