RE (복잡도)

RE(순환 열거)는 '예' 답변을 튜링 기계로 유한한 시간에 검증할 수 있는 판정 문제의 집합이다. (답변이 '아니오'인 경우에는 기계가 멈추지 않을 수도 있다.)

RE는 튜링 기계가 모든 '예' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다. 이 정의는 앞쪽 정의랑 동등하다.

RE의 원소는 모두 순환 열거 집합의 원소이기도 하다.

 Co-RE 
co-RE는 RE에 들어 있는 언어의 보완() 언어의 집합이다. '아니오' 답변은 튜링 기계로 유한한 시간에 검증할 수 있지만, '예' 답변은 검증하지 못할 수도 있다.

RE는 튜링 기계가 모든 '아니오' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다.

 같이 보기 
 결정가능성

 외부 링크 
 Complexity Zoo.

분류:복잡도 종류