NP-hard sets are superterse unless NP is small
From MaRDI portal
Publication:290182
DOI10.1016/S0020-0190(96)00189-5zbMath1337.68111MaRDI QIDQ290182
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (4)
The size of SPP ⋮ Comparing reductions to NP-complete sets ⋮ Structural analysis of the complexity of inverse functions ⋮ Some structural properties of SAT
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- P-selectivity: Intersections and indices
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Relativized circuit complexity
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Almost everywhere high nonuniform complexity
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Measure, Stochasticity, and the Density of Hard Languages
- Compressibility and resource bounded measure
- Polynomial-Time Membership Comparable Sets
- Semirecursive Sets and Positive Reducibility
This page was built for publication: NP-hard sets are superterse unless NP is small
