On 1-truth-table-hard languages
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.
- On polynomial time one-truth-table reducibility to a sparse set
- A note on complete problems for complexity classes
- On Sets Truth-Table Reducible to Sparse Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Complete Problems and Strong Polynomial Reducibilities
- A comparison of polynomial time completeness notions
- A comparison of polynomial time reducibilities
- Collapsing degrees
- Complete Problems and Strong Polynomial Reducibilities
- scientific article; zbMATH DE number 176522 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- Indexings of subrecursive classes
- On one-way functions and polynomial-time isomorphisms
- Almost every set in exponential time is P-bi-immune
- Almost complete sets.
- Non-uniform reductions
- Two queries
- Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
- Partial bi-immunity, scaled dimension, and NP-completeness
- Nontriviality for exponential time w.r.t. weak reducibilities
- Almost every set in exponential time is P-bi-immune
- Every polynomial-time 1-degree collapses if and only if P = PSPACE
- Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998
This page was built for publication: On 1-truth-table-hard languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261477)
