P versus NP and computability theoretic constructions in complexity theory over algebraic structures. (English) Zbl 1067.03051

Summary: We show that there is a structure of countably infinite signature with \({\text P} = {\text N}_2{\text P}\) and a structure of finite signature with \({\text P} = {\text N}_1{\text P}\) and \({\text N}_1{\text P} \neq {\text N}_2{\text P}\). We give a further example of a structure of finite signature with \({\text P}\neq {\text N}_1{\text P}\) and \({\text N}_1{\text P}\neq {\text N}_2{\text P}\). Together with a result of P. Koiran [Theor. Comput. Sci. 133, 35–47 (1994; Zbl 0822.68028)] this implies that for each possibility of \({\text P}\) versus \(\text{NP}\) over structures there is an example of countably infinite signature. Then we show that for some finite \(\mathcal L\) the class of \(\mathcal L\)-structures with \({\text P} = {\text N}_1 {\text P}\) is not closed under ultraproducts and obtain as corollaries that this class is not \(\Delta\)-elementary and that the class of \(\mathcal L\)-structures with \({\text P}\neq {\text N}_1{\text 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: \({\text P}\neq {\text N}_1{\text P}\), \({\text N}_1{\text P}\neq {\text N}_2{\text P}\), the levels \({\text N}_2\text{TIME}(n^i)\) of \({\text N}_2{\text P}\) and the levels \({\text N}_1\text{TIME}(n^i)\) of \({\text N}_1{\text P}\) are different for different \(i\), indeed \(\text{DTIME}(n^{i'})\nsubseteq {\text N}_2\text{TIME}(n^i)\) if \(i' > i\); \(\text{DTIME}(f)\nsubseteq {\text N}_2{\text P}\), and \({\text N}_2{\text P}\subseteq \text{DEC}\). \(\text{DEC}\) is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of \({\text N}_2{\text 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.


03D15 Complexity of computation (including implicit computational complexity)
03C10 Quantifier elimination, model completeness, and related topics
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)


Zbl 0822.68028
Full Text: DOI


[1] Model theory (1990)
[2] Models and ultraproducts (1969) · Zbl 0179.31402
[3] Structural complexity 1, 2 (1988)
[4] DOI: 10.1137/0204037 · Zbl 0323.68033
[5] Recursively enumerable sets and degrees (1987)
[6] A model-theoretic proof for P NP over all infinite abelian groups 67 pp 235– (2002) · Zbl 1014.03040
[7] Mathematical logic (1984)
[8] DOI: 10.1002/1521-3870(200101)47:1<67::AID-MALQ67>3.0.CO;2-V · Zbl 0967.03034
[9] DOI: 10.1016/0304-3975(93)00063-B · Zbl 0822.68028
[10] DOI: 10.1002/malq.19980440311 · Zbl 0918.03024
[11] DOI: 10.1002/malq.19980440102 · Zbl 0911.03023
[12] Computability and complexity over structures of finite type (1995)
[13] On structures with proper polynomial time hierarchy (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.