暗黙の計算複雑性

Jones ^{[ 7 ] [ 12 ]}は、入力がバイナリ文字列である決定問題を解くことができるプログラミング言語を定義し、問題がこの言語で決定できるのは、それが P に含まれる場合に限ることを示した。この言語は、簡単に次のように説明できる。入力はビットのリストとして受け取る。リストを指し、末尾操作を適用して変更できる変数があり、リスト上で前進することができる。再帰関数を定義できるが、高階関数はない。重要なことに、データ型コンストラクタはない（そのためcons-freeという名前が付けられている）。入力リストがプログラム全体を通して唯一のデータ構造である。コンストラクタがないため表現力が制限され、計算中にサイズが大きくなる可能性のある補助データ構造の構築が妨げられる。注目すべきことに、この制限によって決定可能な問題のクラスが P の真部分集合に縮小されることはない。P に含まれるすべての問題は、この言語内で決定できる。さらに、この言語のプログラムは指数時間で実行される可能性があるが、多項式時間の問題のみを決定するため、暗黙的な特徴付けは個々のプログラムの実際の実行時間とは無関係である。ジョーンズはまた、非決定性がこの言語に追加された場合（非決定性チューリングマシンのように）、受け入れ可能な問題のクラスは依然として P であることを示した。^{[ 12 ]}

BellantoniとCook ^{[ 6 ]}は、ある種の関数がFPと一致することを示した。これらは、原始再帰関数と同様に、基本関数と既存の関数から新しい関数を構築するための演算子のセットによって定義される関数である。後述するように、原始再帰スキームの代わりに特別な再帰スキームが使用され、さらに、関数の引数は2つの「ソート」に分割される。これは、引数をセミコロンで区切ることによって示される。${\displaystyle f(x_{1},\dots ,x_{k};x_{k+1},\dots ,x_{k+n})}$セミコロンの後に続く引数はセーフと呼ばれます（より直感的な名前は「保護された」かもしれません）。値がセーフな位置に渡されると、その値は大きくなりすぎることはありません。以下の節（3）と（4）の違いに注意してください。プリミティブ再帰関数の定義とのもう1つの重要な違いは、ここでは引数がバイナリ文字列として扱われ、数値後継関数（x' ）とは対照的に、ビットを追加することによって値を増やすことができる（x 0 またはx 1）ことです。

基本的な機能の一覧は以下のとおりです。

合成スキームと再帰スキームを使用して、関数を組み合わせて新しい関数を作成できます。${\displaystyle g,{\vec {r}},{\vec {s}}}$それらの述語構成、${\displaystyle f=g\circ ({\vec {r}};{\vec {s}})}$定義される$${\displaystyle f({\vec {x}};{\vec {y}})=g({\vec {r}}({\vec {x}};);{\vec {s}}({\vec {x}};{\vec {y}})).}$$ 与えられた${\displaystyle g,h_{0},h_{1}}$記法スキーム上の述語的再帰は関数を定義する${\displaystyle f}$による $${\displaystyle {\begin{aligned}f(\varepsilon ,{\vec {x}};{\vec {y}})&=g({\vec {x}};{\vec {y}}),\\f(zi,{\vec {x}};{\vec {y}})&=h_{i}(z,{\vec {x}};{\vec {y}},f(z,{\vec {x}};{\vec {y}})).\end{aligned}}}$$ これは「表記上の再帰」と呼ばれます。なぜなら、各再帰呼び出しで再帰引数の一部を取り除くからです。これは、zからz -1まで進む「値上の再帰」とは対照的です。

例。関数を定義します。${\displaystyle r(x)}$バイナリ文字列xを受け取り、 xと同じ長さの0の文字列を返します。読みやすさのために、関数引数を取得するために技術的に必要な射影関数の呼び出しを省略します。${\displaystyle \pi _{1}^{1}(x)}$関数でxを取得する ${\displaystyle g(x)}$。 $${\displaystyle {\begin{aligned}g(x)&=f(x,x),{\text{where}}\\f(\varepsilon ,x;)&=\varepsilon ,\\f(zi,x;)&=S_{0}(x;f(z,x;)).\end{aligned}}}$$再帰処理で境界付き二項後継演算子を適用できるようにするためには、最初にx のコピーを保持しておく必要があることに注意してください。

Leivant ^{[ 10 ] は}、「データ階層化」に基づく別のアプローチを開発しました。自然数（またはその他のデータ）は階層に分けられ、再帰は階層の順序を尊重する方法でのみ許可されます。階層境界付き再帰で定義可能な関数は、多項式時間で計算可能な関数と一致します。Leivant のフレームワークは Bellantoni–Cook 代数よりも構文的に柔軟で、命令型言語にも自然に拡張できます。

ジラール、セドロフ、スコット^{[ 4 ]}は、線形論理の変種である有界線形論理を導入した。この論理では、縮約規則の使用は多項式項によって制限される。この体系における証明は、カリー・ハワード対応を介して、多項式時間で計算可能な関数に対応する。ジラール^{[ 13 ]}による軽量線形論理に関するその後の研究、バイヨとテルイ^{[ 14 ]}によるその型理論的発展、そしてラフォンのソフト線形論理^{[ 15 ]}は、より簡潔な証明理論を持つ関連体系を生み出し、いずれも指数様相に対する構造的制約によって多項式時間計算を特徴づけている。