Consider \(\Sigma =\{0,1\}\). A tally set is a subset of \(\{1\}^*\). An oracle Turing machine M is polynomially honest if there exists a polynomial \(p: {\mathbb{N}}\to {\mathbb{N}}\) such that for all oracle sets and for all input strings \(x\in \Sigma^*\), if M queries the oracle about a string y, on input x, then \(| x| \leq p(| y|)\). A set A is honest Turing reducible to the set B in polynomial time, and the notation is \(A\leq^ h_ T B\), if there exist a polynomial time-bounded honest Turing machine M such that \(A=L(M,B)\). A set B is \(tally\)-\(\leq^ h_ T\)-minimal if \(B\not\in P\) and if, for all tally sets A, whenever \(A\leq^ h_ T B\), then either \(A\in P\) or \(B\leq^ h_ T A\). A set A is \(\leq^ h_ T\)-one-way with respect to a function f if a) f is computable in polynomial time and is polynomially honest, b) \(A\nleq^ h_ T f^{-1}(A)\), and c) \(f^{-1}(A)\not\in P.\) The authors prove that if \(P=NP\), then there exists a tally set A that is \(\leq^ h_ T\)-minimal, and, conversely, if \(P\neq NP\), then there are nonrecursive \(\leq^ h_ T\)-one-way sets of arbitrary Turing degree. In the last section, the authors present several sets that cannot be \(\leq^ h_ T\)-minimal.
- A uniform approach to obtain diagonal sets in complexity classes
- scientific article; zbMATH DE number 3930984 (Why is no real title available?)
- scientific article; zbMATH DE number 3586480 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Minimal degrees for polynomial reducibilities
- On degrees of recursive unsolvability
- On some natural complete operators
- On the Structure of Polynomial Time Reducibility
- On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
- The structure of the honest polynomial m-degrees
- On computational complexity and honest polynomial degrees
- Minimal degrees for polynomial reducibilities
- The existence of minimal honest polynomial degree below and recursively enumerable degrees
- scientific article; zbMATH DE number 62443 (Why is no real title available?)
- scientific article; zbMATH DE number 4189714 (Why is no real title available?)
- Cook reducibility is faster than Karp reducibility in NP
- Honest polynomial time reducibilities and the \(P=?NP\) problem
This page was built for publication: Honest polynomial degrees and \(P=?NP\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094875)
