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 |
