R (복잡도)

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

계산 복잡도 이론에서 R튜링 기계로 풀 수 있는 결정문제들의 복잡도 종류이다. 여기서 튜링 기계는 모든 재귀 언어의 집합이다. R은 '효율적으로 계산할 수 있는' 함수의 집합으로 보기도 한다. (처치-튜링 명제)

이 집합은 REco-RE의 교집합이다. 어떤 문제에 대한 recogniser와 co-recogniser가 둘 다 존재한다면, 그 문제를 판정할 수 있기 때문이다.

[편집] 바깥 고리



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

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

다른 언어