멀티미디어 지식공작소 | [본문스크랩] P-NP
멀티미디어 지식공작소 위치로그  |  태그  |  미디어로그  |  방명록
icon [본문스크랩] P-NP
낙서장 | 2007. 3. 27. 16:23
출처 블로그 > 깡
원본 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
버젼은 간단히 풀리겠죠?

arrow 트랙백 | 댓글



관리자  |   글쓰기
BLOG main image
- 블로그를 처음 만들면서
분류 전체보기 (142)
기술동향 뉴스 (51)
신조어 사전 (1)
기술용어집 (5)
영상처리 기술 (29)
IT 사용정보 (7)
프로그램 기술 (23)
학술정보 (1)
생활정보 (9)
낙서장 (13)
나의 이야기 (0)
About Me (0)
Total :
Today :
Yesterday :
rss
위치로그 : 태그 : 방명록 : 관리자
multimedia's Blog is powered by Daum / Designed by plyfly.net