Pages that link to "Item:Q1253918"
From MaRDI portal
The following pages link to A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem (Q1253918):
Displayed 22 items.
- Dispersion of mass and the complexity of randomized geometric algorithms (Q947778) (← links)
- Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model (Q1050255) (← links)
- A lower time bound for the knapsack problem on random access machines (Q1052091) (← links)
- Lower bound arguments with ``inaccessible'' numbers (Q1107308) (← links)
- On the limits of computations with the floor function (Q1112603) (← links)
- On selecting the k largest with median tests (Q1115626) (← links)
- Comparisons between linear functions can help (Q1170029) (← links)
- Test complexity of generic polynomials (Q1201154) (← links)
- Verification complexity of linear prime ideals (Q1207526) (← links)
- On the complexity of computations under varying sets of primitives (Q1259164) (← links)
- A lower bound for randomized algebraic decision trees (Q1386178) (← links)
- Simulating probabilistic by deterministic algebraic computation trees (Q1821560) (← links)
- Rough analysis of computation trees (Q2172394) (← links)
- A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model (Q2415377) (← links)
- Open problems around exact algorithms (Q2473037) (← links)
- Time and space complexity of deterministic and nondeterministic decision trees (Q2679423) (← links)
- On computations with integer division (Q3816971) (← links)
- A geometrical method in combinatorial complexity (Q3902478) (← links)
- Computation over algebraic structures and a classification of undecidable problems (Q4593236) (← links)
- Lower bounds on algebraic random access machines (Q4645192) (← links)
- On genuinely time bounded computations (Q5096139) (← links)
- The complexity of linear programming (Q5904560) (← links)