NP (복잡도)

위키백과 ― 우리 모두의 백과사전.

이 문서는 en:NP (complexity)에서 한국어로 번역 중입니다. 원문은 글 안에 주석 처리되어 있습니다. 같이 번역해 주세요.

계산 복잡도 이론에서, NP비결정론적 튜링 기계다항시간에 풀 수 있는 판정문제의 집합이다. 다시 말해, NP는 결정론적 튜링 기계로 다항시간에 '검증'(verify)할 수 있는 문제들의 집합이다. NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다.

목차

[편집] 간단한 예제

이러한 종류의 문제 집합은 검색이나 최적화에 대한 다양하고 흥미로운 문제들을 포함하고 있는데, 이러한 특정한 문제에 대하여 이 문제를 해결할 수 있는 해답이 존재하는지는 아직까지 알려져 있지 않다는 점에서 매우 중요하다.

[편집] 어떤 NP 문제들은 왜 풀기 어려운가

[편집] 특징

[편집] 예제

[편집] 참고문헌

  • Complexity Zoo: NP
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 34.2: Polynomial-time verification, pp.979–983.
  • Michael Sipser, Introduction to the Theory of Computation, ISBN 0-534-94728-X. Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp.241–271.


주요 복잡도 종류 (더 보기)

P | NP | Co-NP | NP-C | Co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C
EXPTIME | EXPSPACE | PR | RE | Co-RE | RE-C | Co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH