P versus NP and computability theoretic constructions in complexity theory over algebraic structures
Mainhardt, Gunther
J. Symbolic Logic, Tome 69 (2004) no. 1, p. 39-64 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We show that there is a structure of countably infinite signature with P=N2P and a structure of finite signature with P=N1P and N1P ≠ N2P. We give a further example of a structure of finite signature with P ≠ N1P and N1P ≠ N2P. Together with a result from [Koiran] 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=N1P is not closed under ultraproducts and obtain as corollaries that this class is not Δ-elementary and that the class of ℒ-structures with P ≠ N1P 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 ≠ N1P, N1P ≠ N2P, the levels N2TIME(ni) of N2P and the levels N1TIME(ni) of N1P are different for different i, indeed DTIME(ni’) ⊈ N2TIME(ni) if i’>i, DTIME(f) ⊈ N2P, and N2P ⊈ DEC. DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of N2P 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.
Publié le : 2004-03-14
Classification:  
@article{1080938824,
     author = {Mainhardt, Gunther},
     title = {P versus 
NP and computability theoretic constructions in complexity theory over algebraic structures},
     journal = {J. Symbolic Logic},
     volume = {69},
     number = {1},
     year = {2004},
     pages = { 39-64},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1080938824}
}

Mainhardt, Gunther. P versus 
NP and computability theoretic constructions in complexity theory over algebraic structures. J. Symbolic Logic, Tome 69 (2004) no. 1, pp.  39-64. http://gdmltest.u-ga.fr/item/1080938824/