R (복잡도)

계산 복잡도 이론에서 R은 튜링 기계로 풀 수 있는 결정 문제들의 복잡도 종류로, 모든 재귀 언어의 집합과 같다. 또한 R은 모든 전역 계산 가능 함수를 모은 집합과 같으므로 '효율적으로 계산할 수 있는' 함수의 집합으로 볼 수 있어 계산 가능성 이론에서 중요시된다. (처치-튜링 명제)

이 집합은 RE와 co-RE의 교집합과 같다. 어떤 문제의 정답과 오답이 모두 인지 가능하다면 그 문제는 결정 가능하기 때문이다.

외부 링크

• Complexity Zoo: RE