P-NP 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Ckdgus2482 (토론 | 기여) 기존의 문서에서 NP-완전문제에 항목이 NP-난해문제에 대한 설명을 기술하고 있어 NP-난해 문제 항목을 추가하여 옮김. 그 설명 또한 보다 명확하게 수정함. |
Ckdgus2482 (토론 | 기여) 편집 요약 없음 |
||
18번째 줄:
==NP-난해 ==
어떤 문제가 주어졌을때, 다른 NP문제의 입력을 그 문제의 입력으로 변환할 수 있는 환산 알고리즘이 존재하고 이 환산 알고리즘은 수행시간이 무시될 수 있을 정도로 빠르다면 이 문제는 [[NP-
이 집합이 중요한 이유는, NP-난해에 속하는 문제 중 하나라도 P에 속한다는 것을 밝힌다면 P=NP를 증명할 수 있기 때문이다.
== NP-완전 ==
NP난해문제이면서 NP문제인 문제는 [[NP-
== 참고 사항 ==
| |||