On P Versus NP for Parameter-Free Programs Over Algebraic Structures

DOI10.1002/1521-3870(200101)47:1%3C67::AID-MALQ67%3E3.0.CO;2-VMaRDI QIDQ2707072zbMATH OpenOpenAlexFDO

Authors Armin Hemmerling

Publication date 28 March 2001

Full work available at URL https://doi.org/10.1002/1521-3870(200101)47:1%3C67::aid-malq67%3E3.0.co;2-v

zbMATH Keywords

complexity classescomputation modelcomputation tree analysisP versus NPparameter-free computationsprograms over algebraic structuresquantifier eliminationstructural complexity theorytime complexity of computations over arbitrary first-order structures

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• P versus NP and computability theoretic constructions in complexity theory over algebraic structures
• On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture
• On relativizations of the P =? NP question for several structures
• Fields of algebraic numbers computable in polynomial time. II
• scientific article; zbMATH DE number 953010

Cited in

(4)

• \(\mathbf P =\mathbf{NP}\) for some structures over the binary words
• Two situations with unit-cost: ordered abelian semi-groups and some commutative rings
• On the complexity of identifying head-elementary-set-free programs
• P versus NP and computability theoretic constructions in complexity theory over algebraic structures

This page was built for publication: On P Versus NP for Parameter-Free Programs Over Algebraic Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2707072)