R (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 R은 튜링 기계로 풀 수 있는 결정문제들의 복잡도 종류이다. 여기서 튜링 기계는 모든 재귀 언어의 집합이다. R은 '효율적으로 계산할 수 있는' 함수의 집합으로 보기도 한다. (처치-튜링 명제)
이 집합은 RE와 co-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 |