Polynomial reducibilities and upward diagonalizations
Data up to Jan 2025
Total Citations Per Year
Abstract
References (11)
Reducibility among Combinatorial Problems
1972 • 10,743 citations
The complexity of theorem-proving procedures
1971 • 6,155 citations
On the Structure of Polynomial Time Reducibility
1975 • 801 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
A comparison of polynomial time reducibilities
1975 • 430 citations
Relativization of questions about log space computability
1976 • 171 citations
On Reducibility to Complex or Sparse Sets
1975 • 71 citations
On some subrecursive reducibilities
1977 • 40 citations
A cornucopia of minimal degrees
1970 • 12 citations
Two results on polynomial-time reducibilities
1976 • 3 citations