Counting problems over the reals

The complexity of computing the permanent

Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations

Computing, Computer Science, Mathematics +9

Optimization, approximation, and complexity classes

Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1991 · 1.7K citations

Computing, Computer Science, Mathematics +12

On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

Lenore Blum, M. Shub, Steve Smale · Bulletin of the American Mathematical Society · 1989 · 1.1K citations · Full text

Computing, Computer Science, Mathematics +17

Generalized first-order spectra and polynomial-time recognizable sets

Ronald Fagin · Medical Entomology and Zoology · 1974 · 834 citations

Natural Sciences, Computer Science, Mathematics +9

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 reals

James Renegar · Journal of Symbolic Computation · 1992 · 622 citations

Computing, Computer Science, Mathematics +14