On polynomial time one-truth-table reducibility to a sparse set

DOI10.1016/0022-0000(92)90015-BzbMath0746.68036MaRDI QIDQ1191028

Osamu Watanabe

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

reducibilitystructural complexityrelations among complexity classes

Mathematics Subject Classification ID

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