On polynomial time one-truth-table reducibility to a sparse set
From MaRDI portal
Publication:1191028
DOI10.1016/0022-0000(92)90015-BzbMath0746.68036MaRDI QIDQ1191028
Publication date: 27 September 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
Space-efficient recognition of sparse self-reducible languages ⋮ On characterizing the existence of partial one-way permutations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- On some natural complete operators
- NP is as easy as detecting unique solutions
- On hardness of one-way functions
- On one-way functions and polynomial-time isomorphisms
- Collapsing degrees
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- Complete sets and the polynomial-time hierarchy
- A Note on Sparse Complete Sets
- On intractability of the classUP
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Complexity Measures for Public-Key Cryptosystems
- Natural Self-Reducible Sets
- On Sets Truth-Table Reducible to Sparse Sets
- Cryptocomplexity and NP-completeness
- Complete sets and closeness to complexity classes
This page was built for publication: On polynomial time one-truth-table reducibility to a sparse set
