전체(복잡성)

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "완전한" 복잡성 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2008년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

계산 복잡성 이론에서, 기술적 의미에서, 복잡성 클래스의 "가장 어려운" (또는 "가장 표현력 있는") 문제들 중 하나라면, 복잡한 클래스에 대한 계산 문제가 완성된다.

좀 더 형식적으로, 문제 p는 C에서 p로 (주어진 유형의) 어떤 문제에서 (주어진 유형의) 감소가 존재하는 경우, 주어진 유형의 감소를 받는 복잡성 등급 C에 대해 하드라고 불린다.만약 문제가 학급과 학급 구성원 모두에게 어렵다면, 그것은 그 학급에 대해 완성된다. (그런 유형의 감축에 대해서는)

등급 C에 대해 완료되는 문제는 C-완료라고 하며, C에 대해 완료된 모든 문제의 등급은 C-완료라고 한다.가장 먼저 정의되고 가장 잘 알려진 완전한 클래스는 NP-완전이며, 실제로 발생하는 해결이 어려운 많은 문제들을 포함하고 있는 클래스다.마찬가지로, C등급에게 어려운 문제를 C-hard라고 한다. 예를 들어 NP-hard.

일반적으로, 문제의 감소는 클래스 자체보다 더 높은 계산 복잡성을 가지지 않는다고 가정한다.따라서 C-완전성 문제가 "계산적으로 쉬운" 해결책이 있다면, "C"의 모든 문제는 "쉬운" 해결책이 있다고 할 수 있다.

일반적으로 재귀 열거가 있는 복잡성 클래스는 완전한 문제를 알고 있었지만, 재귀 열거가 없는 클래스는 전혀 없다.예를 들어, NP, co-NP, PLS, PPA는 모두 자연적으로 완전한 문제를 알고 있는 반면, RP, ZPP, BPP, TFNP는 알려진 완전한 문제를 가지고 있지 않다(이러한 문제는 미래에 발견될 수 있지만).^{[citation needed]}

완전한 문제가 없는 수업이 있다.예를 들어 Sipser는 BPP^M(오라클 M이 있는 BPP)가 완전한 문제가 없는 언어 M이 있음을 보여주었다.^[1]

참조