A simple function that requires exponential size read-once branching programs (Q287023): Difference between revisions

@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+P05
@@ Property / Mathematics Subject Classification ID: 68P05 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q05
@@ Property / Mathematics Subject Classification ID: 68Q05 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6585393
@@ Property / zbMATH DE Number: 6585393 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+computational complexity
@@ Property / zbMATH Keywords: computational complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+read-once branching programs
@@ Property / zbMATH Keywords: read-once branching programs / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+projective planes
@@ Property / zbMATH Keywords: projective planes / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for read-once-only branching programs
+Normal rank
@@ Property / cites work @@
+On lower bounds for read-\(k\)-times branching programs
+Normal rank
@@ Property / cites work @@
+Q3694708
@@ Property / cites work: Q3694708 / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Entropy of contact circuits and lower bounds on their complexity
+Normal rank
@@ Property / cites work @@
+A note on read-$k$ times branching programs
@@ Property / cites work: A note on read-$k$ times branching programs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3821583
@@ Property / cites work: Q3821583 / rank @@
+Normal rank
@@ Property / cites work @@
+Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
+Normal rank
@@ Property / cites work @@
+Q4234058
@@ Property / cites work: Q4234058 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4287364
@@ Property / cites work: Q4287364 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of branching programs and decision trees for clique functions
+Normal rank
@@ Property / cites work @@
+Q3762226
@@ Property / cites work: Q3762226 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3347300
@@ Property / cites work: Q3347300 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:287023