Abstract

We show that there is a structure of countably infinite signature with $P = N_{2}P$ and a structure of finite signature with $P = N_{1}P$ and $N_{1}P \neq N_{2}P$ . We give a further example of a structure of finite signature with $P \neq N_{1}P$ and $N_{1}P \neq N_{2}P$ . Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for some finite ℒ the class of ℒ-structures with $P = N_{1}P$ is not closed under ultraproducts and obtain as corollaries that this class is not $\delta$ -elementary and that the class of ᵍ-structures with $P \neq N_{1}P$ is not elementary. Finally we prove that for all f dominating all polynomials there is a structure of finite signature with the following properties: $P \neq N_{1}P$ . $N_{1}P \neq N_{2}P$ , the levels $N_{2}TIME(n^{i})$ of $N_{2}P$ and the levels $N_{1}TIME(n^{i})$ of $N_{1}P$ are different for different i, indeed $DTIME(n^{i'}) \nsubseteq N_{2}TIME(n^{i})$ if $i' \textgreater i$ ; $DTIME(f) \nsubseteq N_{2}P$ , and $N_{2}P \nsubseteq DEC$ . DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of $N_{2}P$ is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts