R (복잡도) 문서 원본 보기

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

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

== 외부 링크 ==
* [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#re Complexity Zoo: RE]

{{복잡도 종류}}
{{위키데이터 속성 추적}}
{{토막글|컴퓨터 과학}}

[[분류:복잡도 종류]]