Journal of Computer and System Sciences · 2010 · 288 citations · 19 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationApproximation AlgorithmsCircuit ComplexityComputational ComplexityHash FunctionsInteger ProgrammingParameterized AlgorithmsBoolean SatisfiabilityCompleteness ResultsComplexity-theoretic ReductionsNp-complete ProblemsNp-completenessOne-way FunctionsOne-way Hash FunctionsPolynomial Time Complexity
19
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM · 1998 · 1.4K citations · Full text
Probabilistic checking of proofs
Sanjeev Arora · Journal of the ACM · 1998 · 1.2K citations · Full text
<i>P = BPP</i> if <i>E</i> requires exponential circuits
Russell Impagliazzo, Avi Wigderson · 1997 · 544 citations