NP-hard sets are superterse unless NP is small

DOI10.1016/S0020-0190(96)00189-5zbMATH Open1337.68111MaRDI QIDQ290182FDOQ290182

Authors Y. 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)

Recommendations

• Approximable sets
• On symmetric differences of NP-hard sets with weakly P-selective sets
• On the size of classes with weak membership properties
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• NONDETERMINISTICALLY SELECTIVE SETS

Cites work

• scientific article; zbMATH DE number 1555954 (Why is no real title available?)
• scientific article; zbMATH DE number 1414313 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• Almost everywhere high nonuniform complexity
• Compressibility and resource bounded measure
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Measure, Stochasticity, and the Density of Hard Languages
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• P-selectivity: Intersections and indices
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Polynomial-Time Membership Comparable Sets
• Relativized circuit complexity
• Semirecursive Sets and Positive Reducibility
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)

Cited in

(7)

• Comparing reductions to NP-complete sets
• Some structural properties of SAT
• Mathematical Foundations of Computer Science 2004
• Polynomial terse sets
• Structural analysis of the complexity of inverse functions
• Approximable sets
• The size of SPP

This page was built for publication: NP-hard sets are superterse unless NP is small

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290182)