A lower bound for randomized algebraic decision trees (Q1386178): Difference between revisions

@@ 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 @@
+On randomized semi-algebraic test complexity
@@ Property / cites work: On randomized semi-algebraic test complexity / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
+Normal rank
@@ Property / cites work @@
+Q3772828
@@ Property / cites work: Q3772828 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228517
@@ Property / cites work: Q4228517 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
+Normal rank
@@ Property / cites work @@
+Solving systems of polynomial inequalities in subexponential time
+Normal rank
@@ Property / cites work @@
+Q5621733
@@ Property / cites work: Q5621733 / rank @@
+Normal rank
@@ Property / cites work @@
+Point location in arrangements of hyperplanes
@@ Property / cites work: Point location in arrangements of hyperplanes / rank @@
+Normal rank
@@ Property / cites work @@
+A Polynomial Linear Search Algorithm for the             <i>n</i>             -Dimensional Knapsack Problem
+Normal rank
@@ Property / cites work @@
+Lower bounds for solving linear diophantine equations on random access machines
+Normal rank
@@ Property / cites work @@
+Simulating probabilistic by deterministic algebraic computation trees
+Normal rank
@@ Property / cites work @@
+The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
+Normal rank
@@ Property / cites work @@
+Lower bounds on probabilistic linear decision trees
+Normal rank
@@ Property / cites work @@
+Lower bounds for algebraic decision trees
@@ Property / cites work: Lower bounds for algebraic decision trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q5807665
@@ Property / cites work: Q5807665 / rank @@
+Normal rank
@@ Property / cites work @@
+A Lower Bound to Finding Convex Hulls
@@ Property / cites work: A Lower Bound to Finding Convex Hulls / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230349
@@ Property / cites work: Q4230349 / rank @@
+Normal rank
@@ Property / cites work @@
+Decision tree complexity and Betti numbers
@@ Property / cites work: Decision tree complexity and Betti numbers / rank @@
+Normal rank