On gamma-reducibility versus polynomial time many-one reducibility

DOI10.1016/0304-3975(81)90007-4zbMath0454.68031OpenAlexW1974647909MaRDI QIDQ1149766

Timothy J. Long

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90007-4

zbMATH Keywords

equivalence of complexity classesgamma-reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Nondeterministic functions and the existence of optimal proof systems, One-way functions and circuit complexity, Comparing reductions to NP-complete sets, Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems, On sparse hard sets for counting classes, Strong nondeterministic polynomial-time reducibilities

Cites Work

• Unnamed Item
• A comparison of polynomial time reducibilities
• Relative complexity of checking and evaluating
• The complexity of theorem-proving procedures