P and NP (P NP 문제)

P문제란?

다항시간 내(reasonable time)에 답을 구할 수 있다.

다루기 쉬운 문제

결정론적 다항시간 문제

 

NP문제란?

Nondeterministic Plynomial time

다항시간 내 풀 수 없는 문제

다항시간내에 풀 수 있는지 없는지 모른다. 

다루기 어려운 문제

비결정론적 다항시간 문제 -> 적어도 검산은 쉽게 할 수 있는 문제. 하지만 답을 찾기는 어려운 문제

 

Unsolvable problems

어떤 알고리즘으로도 풀 수 없는문제

 

 

Optimization/Decision problems

 

Hamiltonian paths and cycles

 

Traveling salesman problem

 

 

Is P=NP?

P⊆NP

P=NP라면? 복잡하고 어려운 문제들을 다항시간 내에 반드시 풀 수 있다. 하지만 NP를 P로 바꾸는 알고리즘이 존재한다는 것만을 알게되는 것이고 그 알고리즘을 찾는 일은 어려울 수 있다.

P=NP가 증명되면 알고리즘을 찾는 일은 어렵다 하더라도 찾으려는 노력이 의미있는 일이 된다.

P≠NP라면?

찾으려고 노력할 필요가 없다.