A comparison of polynomial time reducibilities
Data up to Jan 2025
Total Citations Per Year
Abstract
References (12)
Reducibility among Combinatorial Problems
1972 • 10,743 citations
The complexity of theorem-proving procedures
1971 • 6,155 citations
Theory of Recursive Functions and Effective Computability.
1969 • 2,849 citations
Theory of Recursive Functions and Effective Computability
1969 • 2,654 citations
Formal Languages and Their Relation to Automata
1969 • 1,384 citations
Formal Languages and their Relation to Automata
1970 • 964 citations
Recursively enumerable sets of positive integers and their decision problems
1944 • 883 citations
On the Structure of Polynomial Time Reducibility
1975 • 801 citations
The equivalence problem for regular expressions with squaring requires exponential space
1972 • 620 citations
Complexity of Computer Computations
1974 • 215 citations
Computational Work and Time on Finite Machines
1972 • 106 citations
Relativization of the theory of computational complexity
1976 • 32 citations