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)

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

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)

Cites Work

• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Relativized circuit complexity
• 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
• Title not available (Why is that?)
• Compressibility and resource bounded measure
• Polynomial-Time Membership Comparable Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Semirecursive Sets and Positive Reducibility
• 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}\)

Cited In (7)

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

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)