PR(복잡성)
PR (complexity)PR은 모든 원시 재귀 함수의 복잡도 등급 또는 동등하게, 그러한 함수에 의해 제한되는 시간 내에 결정할 수 있는 모든 공식 언어의 집합이다.이것은 덧셈, 곱셈, 지수, 테트레이션 등을 포함한다.
Ackermann 함수는 원시 재귀성이 아닌 함수의 예로서, PR이 R(Cooper 2004:88)에 엄격히 포함되어 있음을 보여준다.
반면에, 우리는 다음과 같은 의미에서 원시-재귀 함수에 의해 재귀적으로 열거할 수 있는 집합(복잡성 등급 RE 참조)을 "적용"할 수 있다. 여기서 M은 튜링 기계이고 k는 정수인 입력(M, k)이다. M은 k 단계 내에서 정지한 다음 M을 출력한다. 그렇지 않으면 아무것도 출력하지 않는다.그러면 가능한 모든 입력(M, k)에 걸쳐 출력 조합이 정확히 정지하는 M의 집합이다.
PR에는 ENTERIC이 엄격히 포함되어 있다.
PR은 "PR-완전" 문제(예: ENTERIC에 속하는 감소)를 포함하지 않는다. PR에 있지 않고 바로 그 너머에 있는 많은 문제들은 {\{\ -complete (Schmitz 2016)이다.
참조
- S. Barry Cooper (2004). Computability Theory. Chapman & Hall. ISBN 1-58488-237-9.
- Herbert Enderton (2011). Computability Theory. Academic Press. ISBN 978-0-12-384-958-8.
- Schmitz, Sylvain (2016). "Complexity Hierarchies beyond Elementary". ACM Transactions on Computation Theory. 8: 1–36. arXiv:1312.5686. doi:10.1145/2858784.
