R (복잡도)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

바깥 고리[편집]