The size of SPP (Q596117): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2004.02.029
+Normal rank
@@ Property / OpenAlex ID @@
+W2053749801
@@ Property / OpenAlex ID: W2053749801 / rank @@
+Normal rank
@@ Property / cites work @@
+Separating NP-completeness notions under strong hypotheses
+Normal rank
@@ Property / cites work @@
+Q4348122
@@ Property / cites work: Q4348122 / rank @@
+Normal rank
@@ Property / cites work @@
+On pseudorandomness and resource-bounded measure
@@ Property / cites work: On pseudorandomness and resource-bounded measure / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Isomorphism is in SPP
@@ Property / cites work: Graph Isomorphism is in SPP / rank @@
+Normal rank
@@ Property / cites work @@
+Fine Separation of Average-Time Complexity Classes
+Normal rank
@@ Property / cites work @@
+Gap-definable counting classes
@@ Property / cites work: Gap-definable counting classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4289278
@@ Property / cites work: Q4289278 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4359457
@@ Property / cites work: Q4359457 / rank @@
+Normal rank
@@ Property / cites work @@
+MAX3SAT is exponentially hard to approximate if NP has positive dimension.
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+Normal rank
@@ Property / cites work @@
+The Complexity and Distribution of Hard Problems
@@ Property / cites work: The Complexity and Distribution of Hard Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
+Normal rank
@@ Property / cites work @@
+Relative to a random oracle, NP is not small
@@ Property / cites work: Relative to a random oracle, NP is not small / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+Almost everywhere high nonuniform complexity
@@ Property / cites work: Almost everywhere high nonuniform complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Observations on measure and lowness for \(\Delta_ 2^ p\)
+Normal rank
@@ Property / cites work @@
+Q4359463
@@ Property / cites work: Q4359463 / rank @@
+Normal rank
@@ Property / cites work @@
+Measure, Stochasticity, and the Density of Hard Languages
+Normal rank
@@ Property / cites work @@
+Cook versus Karp-Levin: Separating completeness notions if NP is not small
+Normal rank
@@ Property / cites work @@
+Q4266481
@@ Property / cites work: Q4266481 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4501544
@@ Property / cites work: Q4501544 / rank @@
+Normal rank
@@ Property / cites work @@
+The Density of Weakly Complete Problems under Adaptive Reductions
+Normal rank
@@ Property / cites work @@
+Almost every set in exponential time is P-bi-immune
+Normal rank
@@ Property / cites work @@
+Q4938667
@@ Property / cites work: Q4938667 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Complete distributional problems, hard languages, and resource-bounded measure
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+The zero-one law holds for BPP
@@ Property / cites work: The zero-one law holds for BPP / rank @@
+Normal rank
@@ Property / cites work @@
+Q4370033
@@ Property / cites work: Q4370033 / rank @@
+Normal rank
@@ Property / cites work @@
+NP-hard sets are superterse unless NP is small
@@ Property / cites work: NP-hard sets are superterse unless NP is small / rank @@
+Normal rank