On sparse hard sets for counting classes (Q1210293): Difference between revisions

@@ Property / cites work @@
+Q3765251
@@ Property / cites work: Q3765251 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3692867
@@ Property / cites work: Q3692867 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic polynomial time is closed under parity reductions
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+On Sets Truth-Table Reducible to Sparse Sets
@@ Property / cites work: On Sets Truth-Table Reducible to Sparse Sets / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of parity polynomial time
@@ Property / cites work: On the power of parity polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Intersection Theorems for Systems of Sets
@@ Property / cites work: Intersection Theorems for Systems of Sets / rank @@
+Normal rank
@@ Property / cites work @@
+PP is closed under truth-table reductions
@@ Property / cites work: PP is closed under truth-table reductions / rank @@
+Normal rank
@@ Property / cites work @@
+A Note on Sparse Complete Sets
@@ Property / cites work: A Note on Sparse Complete Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+Distinguishing conjunctive and disjunctive reducibilities by sparse sets
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+On gamma-reducibility versus polynomial time many-one reducibility
+Normal rank
@@ Property / cites work @@
+Strong nondeterministic polynomial-time reducibilities
+Normal rank
@@ Property / cites work @@
+Self-reducible sets of small density
@@ Property / cites work: Self-reducible sets of small density / rank @@
+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 Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
+Normal rank
@@ Property / cites work @@
+Q4743737
@@ Property / cites work: Q4743737 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic complexity classes and lowness
@@ Property / cites work: Probabilistic complexity classes and lowness / rank @@
+Normal rank
@@ Property / cites work @@
+Q4139697
@@ Property / cites work: Q4139697 / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q4035673
@@ Property / cites work: Q4035673 / rank @@
+Normal rank
@@ Property / cites work @@
+Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of combinatorial problems with succinct input representation
+Normal rank
@@ Property / cites work @@
+Q3826109
@@ Property / cites work: Q3826109 / rank @@
+Normal rank
@@ Property / cites work @@
+Complete sets and the polynomial-time hierarchy
@@ Property / cites work: Complete sets and the polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank
@@ Property / cites work @@
+On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(93)90020-t
+Normal rank
@@ Property / OpenAlex ID @@
+W1995286703
@@ Property / OpenAlex ID: W1995286703 / rank @@
+Normal rank