P versus NP and computability theoretic constructions in complexity theory over algebraic structures

DOI10.2178/jsl/1080938824zbMath1067.03051OpenAlexW2102403322MaRDI QIDQ5313380

Gunther Mainhardt

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1080938824

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

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

Related Items

\(\mathbf P =\mathbf{NP}\) for some structures over the binary words ⋮ On Relativizations of the P =? NP Question for Several Structures

Cites Work

• Unnamed Item
• Computing over the reals with addition and order
• On P Versus NP for Parameter-Free Programs Over Algebraic Structures
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Computability Over Structures of Infinite Signature
• Computability of String Functions Over Algebraic Structures Armin Hemmerling
• A model-theoretic proof for P ≠ NP over all infinite abelian group