RE-완전

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

RE-완전은 복잡도 종류 RE에서 완전한 결정 문제의 집합이다. 완전하다는 용어의 뜻은 NP-완전 같이 다른 xx-완전 복잡도 종류에서 쓰는 뜻과 같다. RE-완전은 순환 열거 문제 중에서 "가장 어려운" 문제의 집합이라고도 할 수 있다.


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

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

다른 언어