PR（複雑さ）

PR は、すべての原始再帰関数の複雑性クラスです。つまり、そのような関数によって制限された時間内に決定できるすべての形式言語の集合です。これには、加算、乗算、累乗、テトレーションなどが含まれます。

アッカーマン関数は原始再帰ではない関数の例であり、PR がRに厳密に含まれることを示している(Cooper 2004:88)。

一方、再帰的に列挙可能な任意の集合（その複雑性クラスREも参照）を、次の意味で原始再帰関数によって「列挙」することができます。入力 ( M、  k ) が与えられ、ここでMはチューリングマシン、k は整数であり、M がkステップ以内に停止する場合はM を出力し、それ以外の場合は何も出力しません。すると、すべての可能な入力 ( M、  k )にわたる出力の和集合は、停止するMの集合とまったく同じになります。

PR にはELEMENTARY が厳密に含まれます。

PR には「PR 完全」な問題は含まれません (たとえば、ELEMENTARY に属する還元を想定)。実際には、PR に含まれないが PR のすぐ外側にある多くの問題は-完全です (Schmitz 2016)。 ${\displaystyle {\text{𝐅}}_{\omega}}$

• S. バリー・クーパー (2004)。計算可能性理論。チャップマン＆ホール。ISBN 1-58488-237-9。
• ハーバート・エンダートン (2011)。計算可能性理論。アカデミック・プレス。ISBN 978-0-12-384-958-8。
• Schmitz, Sylvain (2016). 「初等レベルを超える複雑性階層」ACM Transactions on Computation Theory . 8 : 1–36. arXiv : 1312.5686 . doi :10.1145/2858784. S2CID  15155865.

• 複雑動物園：PR。