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

DOI<link itemprop=identifier href="https://doi.org/10.1002/1521-3870(200101)47:1<67::AID-MALQ67>3.0.CO;2-V" /><67::AID-MALQ67>3.0.CO;2-V 10.1002/1521-3870(200101)47:1<67::AID-MALQ67>3.0.CO;2-VzbMath0967.03034OpenAlexW2017722148MaRDI QIDQ2707072

Armin Hemmerling

Publication date: 28 March 2001

Full work available at URL: https://doi.org/10.1002/1521-3870(200101)47:1<67::aid-malq67>3.0.co;2-v

zbMATH Keywords

quantifier eliminationcomplexity classescomputation modelstructural complexity theoryP versus NPcomputation tree analysisparameter-free computationsprograms over algebraic structurestime complexity of computations over arbitrary first-order structures

Mathematics Subject Classification ID

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

Related Items (3)

\(\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

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