NP Predicates Computable in the Weakest Level of the Grzegorczyck Hierarchy
Cristian Grozea · Journal of automata, languages and combinatorics · 2004
Let $(E_r){r\in N}$ be the hierarchy of Grzegorczyk. Its weakest level, $E_0$ is indeed quite weak, as it does not even contain functions such as $max(x,y)$ or $x+y$. In this paper we show that $SAT\in E_0$ by developing a technique which can be used to show the same result holds for other NP problems. Using this technique, we are able to show that also the Hamiltonian Cycle Problem is solvable in $E_0$.