Bulletin of the European Association for Theoretical Computer Science · 2002 · 33 citations · 10 references
ComputingComputer ScienceMathematicsCombinatoricsGeometryTheory Of ComputationComplexity TheoryComputational ComplexityComplexity-theoretic HardnessComplexity-theoretic ReductionsNp-completenessP Versus Np ProblemPolynomial Time Complexity
We explain the essence of K. Mulmuley and M. Sohoni, “Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems” [MS02] for a general complexity-theory audience. We evaluate the power and prospects of the new approach. The emphasis is not on probing the deep mathematics that underlies this work, but rather on helping computational complexity theorists not versed in its background to understand the combinatorics involved.
10
Completeness classes in algebra
Leslie G. Valiant · 1979 · 487 citations · Full text
Alexander Razborov, Steven Rudich · Journal of Computer and System Sciences · 1997 · 482 citations
Choice Reviews Online · 1996 · 187 citations
Hilbert's Nullstellensatz Is in the Polynomial Hierarchy
Pascal Koiran · Journal of Complexity · 1996 · 89 citations