On Relativizations of the P =? NP Question for Several Structures
From MaRDI portal
Publication:4918006
DOI10.1016/j.entcs.2008.12.008zbMath1262.68043OpenAlexW2132100285MaRDI QIDQ4918006
Publication date: 3 May 2013
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.entcs.2008.12.008
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Computation over the reals, computable analysis (03D78)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- A note on a \(P \neq NP\) result for a restricted class of real machines
- Real number models under various sets of operations
- Separation of complexity classes in Koiran's weak model
- Relativizations of the P=?NP question over the reals (and other ordered rings)
- Computing over the reals with addition and order
- On NP-completeness for linear machines
- \(\mathbf P =\mathbf{NP}\) for some structures over the binary words
- Implicit complexity over an arbitrary structure: Quantifier alternations
- On the Complexity of Quantifier Elimination: the Structural Approach
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH
- P versus NP and computability theoretic constructions in complexity theory over algebraic structures
- Structure with fast elimination of quantifiers
- Fundamentals of Computation Theory
- A system of axiomatic set theory. Part III. Infinity and enumerability. Analysis
- The P-DNP problem for infinite Abelian groups
