Minimal degrees for polynomial reducibilities

DOI10.1145/23005.23009zbMath0639.03046OpenAlexW2090154710MaRDI QIDQ3781091

Homer, Steven

Publication date: 1987

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/23005.23009

zbMATH Keywords

reducibilityminimal degreearithmetic hierarchynonrecursive sets\(P=NP\)

Mathematics Subject Classification ID

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

Related Items

Uniformly hard languages., The structure of the honest polynomial m-degrees, Honest polynomial degrees and \(P=?NP\), Honest polynomial time reducibilities and the \(P=?NP\) problem, Introduction to Autoreducibility and Mitoticity, Kolmogorov complexity and degrees of tally sets, The existence of minimal honest polynomial degree below and recursively enumerable degrees, Strong polynomial-time reducibility, Cook reducibility is faster than Karp reducibility in NP, On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets