NP-hard sets are superterse unless NP is small

DOI10.1016/S0020-0190(96)00189-5zbMath1337.68111MaRDI QIDQ290182

Yongge Wang

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityp-measureP-selective set

Mathematics Subject Classification ID

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