R(복잡성)

계산 복잡성 이론에서 R은 튜링 기계가 해결할 수 있는 의사결정 문제의 등급으로, 모든 재귀 언어의 집합(디커버블 언어라고도 함)이다.

등가제식

R은 다음과 같은 의미에서 모든 계산 가능한 기능의 집합과 동일하다.

• 결정문제는 지시계 함수를 계산할 수 있는 경우에만 R에 있다.
• 전체 함수는 그래프가 R인 경우에만 계산할 수 있다.

타계급과의 관계

단순히 결과를 얻을 때까지 상호연계함으로써 인식자와 공동인식자가 존재하는 문제를 결정할 수 있기 때문에, 등급은 RE ∩ co-RE와 같다.

참조

• Blum, Leenore, Mike Shub, Steve Smale(1989년)은 "실수에 대한 계산과 복잡성의 이론: NP-완전성, 재귀 기능 및 범용 기계에 대하여"로 미국수학협회의 게시판, New Series, 21: 1-46이다.

외부 링크

복잡성 동물원: 클래스 R