Separation of complexity classes in Koiran's weak model
- 1 October 1994
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 133 (1) , 3-14
- https://doi.org/10.1016/0304-3975(94)00069-7
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Computing over the reals with addition and orderTheoretical Computer Science, 1994
- On the Complexity of Quantifier Elimination: the Structural ApproachThe Computer Journal, 1993
- A note on a P ≠ NP result for a restricted class of real machinesJournal of Complexity, 1992
- PR ≠ NCRJournal of Complexity, 1992
- On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the realsJournal of Symbolic Computation, 1992
- Nonuniform proof systems: a new framework to describe nonuniform and probabilistic complexity classesTheoretical Computer Science, 1991
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- Real quantifier elimination is doubly exponentialJournal of Symbolic Computation, 1988