차이점

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

@@ 줄 1: / 줄 1: @@
+====== NP 복잡도 ======
+**N**ondeterministic, **P**olynomial time. [[비결정적튜링기계]](NTM)에서 [[다항시간]] 안에 풀 수 있는 [[결정문제]]의 [[집합]]. [[함수문제]]에 대응되는 복잡도는 **[[FNP복잡도|FNP]]**이다. 가끔씩 NP를 Non-polynomial time으로 착각하는 사람이 있지만 [[지수시간]] 안에 풀 수 있는 문제들의 집합은 [[EXPTIME]]으로 따로 복잡도가 있다.
+비결정적 튜링 기계는 좀 복잡하므로 보통의 결정적 튜링 기계(DTM)를 사용하여 NP를 다시 정의하면, NP는 문제를 풀고 나서 그 문제의 입력, 출력 및 출력이 맞는지 검증하는 데 도와줄 힌트(certificate)를 주면 그 힌트를 사용해서 입출력이 올바른지 다항 시간 안에 검사(verify)할 수 있는 모든 문제의 집합이다. 이 때 힌트로 주는 데이터 역시 그 크기가 입력 길이에 대한 다항식으로 주어져야 한다. 이 정의가 NTM을 사용한 것과 같은 이유는, 이 정의를 그대로 사용하면 NTM이 비결정적으로 힌트를 만들어 낸 뒤에 검사를 해서 맞는 것만 통과시키면((비결정적으로 동작하므로 다항식 길이의 모든 힌트를 다항 시간 안에 테스트할 수 있다!)) 다항 시간만이 걸리기 때문이다.
+[[P복잡도|P]]와 NP는 [[전산학]]에서 가장 중요한 [[복잡도종류]]들이다. 둘 사이의 관계는 [[P=NP]] 문제로 잘 알려진 [[미해결문제]]이고, 또한 전산학에서 많은 문제들이 NP와 깊게 관련된 [[NP-완전]] 또는 [[NP-난해]] 복잡도에 속하는 것으로 알려져 있다.
+{{tag>전산학}}

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