A model-theoretic proof for P ≠ NP over all infinite abelian group
From MaRDI portal
Publication:4532627
DOI10.2178/jsl/1190150041zbMath1014.03040OpenAlexW1514578557MaRDI QIDQ4532627
Publication date: 5 July 2003
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/jsl/1190150041
polynomial time computationsdeterministic and nondeterminestic register machinesmeasure of complexity of a description of information
Model-theoretic algebra (03C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the P-NP problem over real matrix rings, \(\mathbf P =\mathbf{NP}\) for some structures over the binary words, Two situations with unit-cost: ordered abelian semi-groups and some commutative rings, P versus NP and computability theoretic constructions in complexity theory over algebraic structures, Real computational universality: the word problem for a class of groups with infinite presentation