차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

차이 보기로 연결

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>전산학}}

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기