'P-NP' 태그의 글 목록

http://blog.naver.com/gangseok514/130004190721

P class: 시험 시간 안에 풀 수 있는 문제

NP class: (시험 시간 안에 풀 수 있는지는 모르겠지만), 답을 알려주면 맞는지
시간 안에 검산해볼 수 있는 문제

co-NP class: (시험 시간 안에 풀 수 있는지는 모르겠지만), 답을 알려주면
그 답이 틀렸는지 시간 안에 검산해 볼 수 있는 문제.

P에 속하면 당연히 NP에 속합니다.
(왜나면 직접 풀어서 알려준 답과 맞는지 비교하는 것도 검산의 한 방법이니..)

하지만 NP가 P인지는 모릅니다. (검산할 수 있다는 것과 풀 수 있다는 것의
차이...)
-------------------------------------------------------------------------
NP-complete 는 그 중에서 한 문제만 P라고 풀려도 줄줄이 사탕으로 모든 NP
문제가 P로 풀린다는게 증명된 문제들입니다. 당연히 제일(!) 어려운 문제죠.

소수 판정은 NP-complete인지, P인지 다들 모르고 있었지만 다들 어려워하던
문제입니다. 그런데 P에 속한다는 증명이 나온 거죠.

NP-complete가 P에 속한다면, 모든 NP 문제가 P에 속하게 되므로 소수 판정이
P라는 논문은 역사속으로 사라집니다.

하지만 NP 중의 하나라도 P가 아니라고 증명된다면... 꽤 복잡해집니다.
P와 NP의 두 그룹으로 나뉘는게 아니라 그 사이에 자잘한 부류로 나뉩니다.
(조금 어려운 문제, 많이 어려운 문제, 식으로요.)

NP-hard는...
NP class에 속하는지 증명되지는 않았지만, 이 문제가 풀리면 모든 NP 문제가
P에 풀린다고 증명되는 문제의 집합입니다.

즉, 시험 시간 안에 검산할 수는 없지만, 누군가가 맞는 공식을 알려주면
그걸 이용해서 다른 어려운 문제를 풀 수 있는 경우라고나 할까?

50개의 도시를 도는 TSP의 경우
NP-complete는.. "50개의 도시를 1000km 안에 다 돌 수 있느냐?"란 문제겠죠.
누군가가 "A-B-C-D 순으로 돌면 돼"라고 알려주면 그게 맞는지 검산해 볼 수
있습니다.

NP-hard는.. "50개의 도시를 다 도는 가장 짧은 길은 몇 km냐?"죠.
누군가가 "A-B-C-D 순으로 돌면 975 km면 돼"라고 알려준다고 해도 혹시
"B-A-C-D" 순으로 도는게 더 짧을 수도 있으니 검산으로 확인해 볼 수 없죠.

NP-hard 문제인 위 문제를 어떻게든 풀 수 있다면, 위의 NP-complete
버젼은 간단히 풀리겠죠?

티스토리툴바