On Relativizations of the P =? NP Question for Several Structures
Open Access
- 25 December 2008
- journal article
- Published by Elsevier in Electronic Notes in Theoretical Computer Science
- Vol. 221, 71-83
- https://doi.org/10.1016/j.entcs.2008.12.008
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Implicit complexity over an arbitrary structure: Quantifier alternationsInformation and Computation, 2006
- The P-DNP Problem for Infinite Abelian GroupsJournal of Complexity, 2001
- On NP-Completeness for Linear MachinesJournal of Complexity, 1997
- Separation of complexity classes in Koiran's weak modelTheoretical Computer Science, 1994
- Relativizations of the P=?NP question over the reals (and other ordered rings)Theoretical Computer Science, 1994
- On the Complexity of Quantifier Elimination: the Structural ApproachThe Computer Journal, 1993
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- Structural Complexity IPublished by Springer Nature ,1988
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- A system of axiomatic set theory. Part III. Infinity and enumerability. AnalysisThe Journal of Symbolic Logic, 1942