Tally NP sets and easy census functions. (Q1854340): Difference between revisions

@@ Property / cites work @@
+Limitations of the upward separation technique
@@ Property / cites work: Limitations of the upward separation technique / rank @@
+Normal rank
@@ Property / cites work @@
+P-Printable Sets
@@ Property / cites work: P-Printable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy and sparse oracles
@@ Property / cites work: The polynomial-time hierarchy and sparse oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Q4293543
@@ Property / cites work: Q4293543 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting classes: Thresholds, parity, mods, and fewness
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Tally languages and complexity classes
@@ Property / cites work: Tally languages and complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Enumerative counting is hard
@@ Property / cites work: Enumerative counting is hard / 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 @@
+A note on enumerative counting
@@ Property / cites work: A note on enumerative counting / rank @@
+Normal rank
@@ Property / cites work @@
+Gap-definable counting classes
@@ Property / cites work: Gap-definable counting classes / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Scalability and the isomorphism problem
@@ Property / cites work: Scalability and the isomorphism problem / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+On the construction of parallel computers from various basis of Boolean functions
+Normal rank
@@ Property / cites work @@
+Compression and Ranking
@@ Property / cites work: Compression and Ranking / rank @@
+Normal rank
@@ Property / cites work @@
+On sparse sets in NP-P
@@ Property / cites work: On sparse sets in NP-P / rank @@
+Normal rank
@@ Property / cites work @@
+The strong exponential hierarchy collapses
@@ Property / cites work: The strong exponential hierarchy collapses / rank @@
+Normal rank
@@ Property / cites work @@
+Relations among MOD-classes
@@ Property / cites work: Relations among MOD-classes / rank @@
+Normal rank
@@ Property / cites work @@
+A Downward Collapse within the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Defying upward and downward separation
@@ Property / cites work: Defying upward and downward separation / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean operations, joins, and the extended low hierarchy
+Normal rank
@@ Property / cites work @@
+On the complexity of ranking
@@ Property / cites work: On the complexity of ranking / rank @@
+Normal rank
@@ Property / cites work @@
+Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
+Normal rank
@@ Property / cites work @@
+Easy sets and hard certificate schemes
@@ Property / cites work: Easy sets and hard certificate schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Computation times of NP sets of different densities
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativized Polynomial Time Hierarchies Having Exactly <i>K</i> Levels
+Normal rank
@@ Property / cites work @@
+On Circuit-Size Complexity and the Low Hierarchy in NP
+Normal rank
@@ Property / cites work @@
+On counting and approximation
@@ Property / cites work: On counting and approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines with few accepting computations and low sets for PP
+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 Restricting the Size of Oracles Compared with Restricting Access to Oracles
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+A complexity theory for feasible closure properties
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4743737
@@ Property / cites work: Q4743737 / rank @@
+Normal rank
@@ Property / cites work @@
+Upward separation for FewP and related classes
@@ Property / cites work: Upward separation for FewP and related classes / rank @@
+Normal rank
@@ Property / cites work @@
+A low and a high hierarchy within NP
@@ Property / cites work: A low and a high hierarchy within NP / rank @@
+Normal rank
@@ Property / cites work @@
+Graph isomorphism is in the low hierarchy
@@ Property / cites work: Graph isomorphism is in the low hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: 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 @@
+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 @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+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 Enumeration and Reliability Problems
+Normal rank
@@ Property / cites work @@
+Q3140234
@@ Property / cites work: Q3140234 / rank @@
+Normal rank