이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
np-완전 [2010-03-06 05:15] lifthrasiir 새로 만듦 |
np-완전 [2011-05-30 18:25] (현재) |
||
---|---|---|---|
줄 3: | 줄 3: | ||
[[en>NP-complete]]. NP-C라고도 씀. | [[en>NP-complete]]. NP-C라고도 씀. | ||
- | [[NP]]에 속하면서 다른 모든 NP 문제보다 적어도 쉽지 않은 문제들이 속한다. NP에 속하지는 않고 후자임이 알려진 문제는 [[NP-난해]]라고 함. | + | [[NP복잡도|NP]]에 속하면서 다른 모든 NP 문제보다 적어도 쉽지 않은 문제들이 속한다. NP에 속하지는 않고 후자임이 알려진 문제는 [[NP-난해]]라고 함. |
- | NP-완전한 문제는 [[P=NP]]가 증명되지 않는 한 다항 시간 안에 풀 수 없지만 그렇다고 항상 지수 시간이 걸리는 건 아니다. 지수 시간이 걸리는 문제의 집합은 [[EXPTIME]]이며 NP = EXPTIME인지는 [[미해결문제]]임. | + | NP-완전한 문제는 [[P=NP]]가 증명되지 않는 한 다항 시간 안에 풀 수 없지만 그렇다고 항상 지수 시간이 걸리는 건 아니다. 지수 시간이 걸리는 문제의 집합은 [[EXPTIME]]이며 NP = EXPTIME인지는 [[미해결문제]]임. 즉 재수 없으면 다항과 지수 사이에 있는 것들이 걸릴 수도 있... |
+ | |||
+ | {{tag>전산학}} |