Complete sets and the polynomial-time hierarchy
Data up to Jan 2025
Total Citations Per Year
Abstract
References (13)
Reducibility among Combinatorial Problems
1972 • 10,743 citations
The Design and Analysis of Computer Algorithms
1974 • 9,688 citations
The complexity of theorem-proving procedures
1971 • 6,155 citations
Complexity of Computer Computations
1972 • 2,804 citations
The polynomial-time hierarchy
1976 • 1,332 citations
Word problems requiring exponential time(Preliminary Report)
1973 • 865 citations
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
1975 • 750 citations
The equivalence problem for regular expressions with squaring requires exponential space
1972 • 620 citations
Space-bounded reducibility among combinatorial problems
1975 • 371 citations
Time- and tape-bounded turing acceptors and AFLs
1970 • 72 citations
Relativization of the theory of computational complexity
1976 • 32 citations
NONDETERMINISTIC TIME AND SPACE COMPLEXITY CLASSES
1974 • 16 citations
Thirteenth annual IEEE Symposium on switching and automata theory
1974 • 3 citations