R (복잡도)

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

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

[편집] 바깥 고리