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

@@ Property / Mathematics Subject Classification ID @@
+Q15
@@ Property / Mathematics Subject Classification ID: 68Q15 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+D30
@@ Property / Mathematics Subject Classification ID: 03D30 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6588275
@@ Property / zbMATH DE Number: 6588275 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+computational complexity
@@ Property / zbMATH Keywords: computational complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+P-selective set
@@ Property / zbMATH Keywords: P-selective set / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+p-measure
@@ Property / zbMATH Keywords: p-measure / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q4525724
@@ Property / cites work: Q4525724 / rank @@
+Normal rank
@@ Property / cites work @@
+Compressibility and resource bounded measure
@@ Property / cites work: Compressibility and resource bounded measure / rank @@
+Normal rank
@@ Property / cites work @@
+P-selectivity: Intersections and indices
@@ Property / cites work: P-selectivity: Intersections and indices / rank @@
+Normal rank
@@ Property / cites work @@
+Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
+Normal rank
@@ Property / cites work @@
+Semirecursive Sets and Positive Reducibility
@@ Property / cites work: Semirecursive Sets and Positive Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+Almost everywhere high nonuniform complexity
@@ Property / cites work: Almost everywhere high nonuniform complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Cook versus Karp-Levin: Separating completeness notions if NP is not small
+Normal rank
@@ Property / cites work @@
+Measure, Stochasticity, and the Density of Hard Languages
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Membership Comparable Sets
@@ Property / cites work: Polynomial-Time Membership Comparable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Q4942650
@@ Property / cites work: Q4942650 / rank @@
+Normal rank
@@ Property / cites work @@
+On polynomial-time truth-table reducibility of intractable sets to P-selective sets
+Normal rank
@@ Property / cites work @@
+Q5284998
@@ Property / cites work: Q5284998 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativized circuit complexity
@@ Property / cites work: Relativized circuit complexity / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:290182