[알고리즘] NP problem & P problem

(2021.12.14)

알고리즘 수업 들으면서 정리하기 26탄 

 

w15-2 녹강 + 보충강의 정리

 

저번 시간에 배우던 solvable problem 나머지 부분에 대해서 배웠따

개념이 너무 뒤죽박죽함

---

 

▷ solvable problems

> provably intractable problems (infeasible) : 해결하기 어려움이 입증된 문제

> probably intractable problems : 아마도 해결하기 어려울 것 같은 문제  ---> NP

> tractable problems (feasible) : 다루기 쉬운 문제  --> P

 

 

 

▷ deterministic turing machine(DTM)

: 주어진 state, 주어진 input 에 대해서 하나의 possible action만 존재하는 것

▷ nondeterministic turing machine(NTM)

: 주어진 state, 주어진 input 에 대해서 하나 이상의 possible action이 존재하는 것

(DTM ⊆ NTM)

 

 

P problem은 Class of deterministic Polynomial-time problem (O(n^k))

NP problem은 Class of Nondeterministic Polynomial-time problem

 

 

 

 

▷ NP class of problem

> Decision problem: yes or no (decision problem 인가요?)

> Certificate whose length are polynomial in the size of the problem (certificate가 있나요?)

> algorithm verifies certificates in polynomial in the size of the problem (cerificate를 verify할 수 있는 알고리즘이 있나요?  --> polynomial time에 풀리는지)

 

P ⊂ NP 

그러나 P가 아닌 NP를 발견하지 못하여 P=NP 인가 하는 질문이 남아있다.

 

 

예시

 

polynomial과 exponential 차이

 

 

 

+) 보충강의 내용

 

NP-complete problems

> NP-complete problems 는 NP에 속한 문제 중 가장 어려운 문제이다. 

> NP problem 은 NP-complete problem 으로 reduce(환원)할 수 있다.

> 예로 곱셈문제를 NP, 덧셈문제를 NP-complete 라고 둘 수 있다. 

> 어떠한 NP problem을 polynomial-time으로 해결할 수 없을 때, 우리는 그 NP problem 을 NP-complete problem으로 reduce(환원)하여 해결할 수 있다.

 

기호의 방향에 주의해야한다.

:Q를 Q'으로 reduce 시켰다는 의미이다. (Q is polynomial0time reducible to Q')