위키백과 ― 우리 모두의 백과사전.
복잡도 이론에서, R은 튜링 기계로 풀 수 있는 결정문제들의 복잡도 종류이다.
이 집합은 RE와 Co-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
|