Honest polynomial degrees and \(P=?NP\) (Q1094875)

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.