A recursion-theoretic approach to NP (Q639668)

This article contains the first purely recursion-theoretic characterization of NP. Let \(W\) be the word algebra with empty word \(\varepsilon\), constructors \(S_0\) and \(S_1\) and destructor \(P\). The conditional \(C\) is added, called by other authors ``selector''. Let \({\mathcal I}\) be the class of function terms composed by these functions and the projection functions over both input sorts (normal and safe). Let \(\mathrm{ST}_0\) be the closure of \({\mathcal I}\) under the input sorted composition and the recursion notation scheme and \(\mathrm{ST}_1\) the closure of \(\mathrm{ST}_0\) under the input sorted composition and the disjunctive tree recursion scheme. Finally, let \({\mathcal B}(\mathrm{ST}_1)\) be the Boolean part of \(\mathrm{ST}_1\). The author proves that \(\mathrm{NP} = {\mathcal B}(\mathrm{ST}_1)\).