Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy (Q685431): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3360127
@@ Property / cites work: Q3360127 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting classes: Thresholds, parity, mods, and fewness
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+Q4385519
@@ Property / cites work: Q4385519 / 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 @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+On the power of deterministic reductions to C=P
@@ Property / cites work: On the power of deterministic reductions to C=P / rank @@
+Normal rank
@@ Property / cites work @@
+Relations among MOD-classes
@@ Property / cites work: Relations among MOD-classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385525
@@ Property / cites work: Q4385525 / rank @@
+Normal rank
@@ Property / cites work @@
+A circuit-based proof of Toda's theorem
@@ Property / cites work: A circuit-based proof of Toda's theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Q5595902
@@ Property / cites work: Q5595902 / rank @@
+Normal rank
@@ Property / cites work @@
+Rational approximation to \(|x|\)
@@ Property / cites work: Rational approximation to \(|x|\) / rank @@
+Normal rank
@@ Property / cites work @@
+Q4743737
@@ Property / cites work: Q4743737 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Probabilistic complexity classes and lowness
@@ Property / cites work: Probabilistic complexity classes and lowness / 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 @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+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 complexity of combinatorial problems with succinct input representation
+Normal rank
@@ Property / cites work @@
+Q3768891
@@ Property / cites work: Q3768891 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(93)90214-e
+Normal rank
@@ Property / OpenAlex ID @@
+W2081131534
@@ Property / OpenAlex ID: W2081131534 / rank @@
+Normal rank

Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431): Difference between revisions

Latest revision as of 11:11, 30 July 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)