P =NP for some structures over the binary words

DOI10.1016/J.JCO.2005.02.001MaRDI QIDQ2387422zbMATH OpenOpenAlexFDO

Authors Armin Hemmerling

Publication date 2 September 2005

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2005.02.001

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) 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

• On relativizations of the P =? NP question for several structures
• P versus NP and computability theoretic constructions in complexity theory over algebraic structures
• The polynomial hierarchy for some structures over the binary words
• A syntactical definition of the problem
• To the problem P=?NP

Cites work

• P versus NP and computability theoretic constructions in complexity theory over algebraic structures
• A model-theoretic proof for P ≠ NP over all infinite abelian group
• A survey on real structural complexity theory
• Accessible telephone directories
• Algorithmic properties of structures
• Computability of String Functions Over Algebraic Structures Armin Hemmerling
• scientific article; zbMATH DE number 1670470 (Why is no real title available?)
• scientific article; zbMATH DE number 738388 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On P Versus NP for Parameter-Free Programs Over Algebraic Structures
• The P-DNP problem for infinite Abelian groups

Cited in

(3)

• On relativizations of the P =? NP question for several structures
• P versus NP and computability theoretic constructions in complexity theory over algebraic structures
• Structure with fast elimination of quantifiers

This page was built for publication: \(\mathbf P =\mathbf{NP}\) for some structures over the binary words

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