R (복잡도)
보이기
계산 복잡도 이론에서 R은 튜링 기계로 풀 수 있는 결정 문제들의 복잡도 종류로, 모든 재귀 언어의 집합과 같다. 또한 R은 모든 전역 계산 가능 함수를 모은 집합과 같으므로 '효율적으로 계산할 수 있는' 함수의 집합으로 볼 수 있어 계산 가능성 이론에서 중요시된다. (처치-튜링 명제)
이 집합은 RE와 co-RE의 교집합과 같다. 어떤 문제의 정답과 오답이 모두 인지 가능하다면 그 문제는 결정 가능하기 때문이다.
실현 가능 | |
---|---|
실현 불가능 (추측) | |
실현 불가능 |
![]() |
이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |