RE (복잡도)
위키백과 ― 우리 모두의 백과사전.
RE(recursively enumerable 순환 열거)는 '예' 답변을 튜링 기계로 유한한 시간에 검증할 수 있는 판정 문제의 집합이다. (답변이 '아니오'인 경우에는 기계가 멈추지 않을 수도 있다.)
RE는 튜링 기계가 모든 '예' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다. 이 정의는 앞쪽 정의랑 동등하다.
RE의 원소는 모두 순환 열거 집합의 원소이기도 하다.
[편집] 바깥 고리
|
---|
P · NP · co-NP · NP-C · co-NP-C · NP-난해 · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · co-RE · RE-C · co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH |