NP-hard sets are superterse unless NP is small (Q290182): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4525724 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Compressibility and resource bounded measure / rank
 
Normal rank
Property / cites work
 
Property / cites work: P-selectivity: Intersections and indices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Semirecursive Sets and Positive Reducibility / rank
 
Normal rank
Property / cites work
 
Property / cites work: Almost everywhere high nonuniform complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small / rank
 
Normal rank
Property / cites work
 
Property / cites work: Measure, Stochasticity, and the Density of Hard Languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-Time Membership Comparable Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4942650 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On polynomial-time truth-table reducibility of intractable sets to P-selective sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5284998 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relativized circuit complexity / rank
 
Normal rank

Latest revision as of 01:56, 12 July 2024

scientific article
Language Label Description Also known as
English
NP-hard sets are superterse unless NP is small
scientific article

    Statements

    Identifiers