On 1-truth-table-hard languages (Q1261477): Difference between revisions

Consider two sets \(A\) and \(B\) of strings in \(\Sigma^*\). \(A\) is a polynomial-time many-one reducible to \(B\) if there exists a polynomial- time computable function \(f:\Sigma^*\to \Sigma^*\) such that \(x\in A\) iff \(f(x)\in B\). \(A\) is polynomial-time \(1-tt\) reducible to \(B\) if there exists a polynomial-time machine which, for any input \(x\in \Sigma^*\), generates a one-variable Boolean function \(\alpha_ x(\cdot)\) and a string \(g_ x\) such that \(x\in A\) iff \(\alpha_ x(\chi_ B(g_ x))=1\) where \(\chi_ B\) is the characteristic function \(B\). In general, the first reduction is stronger than the second one. Actually, \textit{R. E. Ladner}, \textit{N. A. Lynch} and \textit{A. L. Selman} (1975) showed the existence of \(1-tt\)-comparable, many-one-incomparable set. The authors prove that every \(1-tt\)-complete set in EXP is many-one complete in EXP. This is an interesting result.