기본 P-NP 문제

[주인장]

* P와 NP가 같은 문제인가? 아님 다른 문제인가? 

* 풀기어려운 문제(Intractability) 

- 다항시간(지수)에 해결되는가

* Input Size

3. 문제 종류

* 풀 수 있다고 증명된 것 

- 어떤 알고리즘을 찾아서 해당 알고리즘이 다항시간에 해결된다는 것을 보이면 됨

* 풀 수 없다고 증명된 것

- Halting Problem 

- 몇 개 없음

* 풀리지도 않고 증명도 안되는 문제 

4. NP 이론 

- 아주 어려운 문제에 대해 답을 이야기 했는데.. 맞는지 틀렸는지 판단하기 여러운 경우 

- 답을 만드는데는 어려운데 검증하는데는 쉽다. 

* P 

- P라는 집합은 polynomial-time에 폴수 있는 결정 문제(O/X)

- 프로이드 알고리즘 처럼 다항 시간안에 해결되는 경우

* NP

- polynomial-time에 non-deterministic 하게 풀 수 있는 결정 문제(O/X)

- 문제의 해결 방법을 아직 찾지 못했거나 해결책이 없다고 증명한 경우 

* polynomial-time 알고리즘 : 

- The worst-case time complexity of the algorithm is O(p(n))

- p(n) is polynomial function, where n is the input size 

- n2, n3 인 경우

* polynomial-time non-deterministic 알고리즘

- a non-deterministic algorithm whose verification stage is a polynomial-time algorithm

- verification stage는 다항시간에 해결되는데 전체는 비결정인 경우 (NP)

최적화 문제 -> 결정 문제로 변경하면 해결 NP