Co-RE

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

co-RE는 RE에 들어 있는 언어의 보완(complement) 언어의 집합이다. '아니오' 답변은 튜링 기계로 유한한 시간에 검증할 수 있지만, '예' 답변은 검증하지 못할 수도 있다.

RE는 튜링 기계가 모든 '아니오' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다.

v • d • e 주요 복잡도 종류 (더 보기)
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