Honest polynomial time reducibilities and the \(P=?NP\) problem

DOI10.1016/0022-0000(89)90023-8zbMath0694.68027OpenAlexW2032860310MaRDI QIDQ909455

Ambos-Spies, Klaus

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90023-8

zbMATH Keywords

minimal degreesr.e. setsNPPreducibilitieshonest polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (5)

The theory of the polynomial many-one degrees of recursive sets is undecidable ⋮ Strong polynomial-time reducibility ⋮ On computational complexity and honest polynomial degrees ⋮ Weak completeness notions for exponential time ⋮ On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On degrees of recursive unsolvability
• Honest polynomial degrees and \(P=?NP\)
• Diagonalizations over polynomial time computable sets
• A note on structure and looking back applied to the relative complexity of computable functions
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• A comparison of polynomial time reducibilities
• Three theorems on the degrees of recursively enumerable sets
• Sublattices of the polynomial time degrees
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Bi-immune sets for complexity classes
• Minimal degrees for polynomial reducibilities
• Strong reducibilities
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability

This page was built for publication: Honest polynomial time reducibilities and the \(P=?NP\) problem