Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On Simplex Pivoting Rules and Complexity Theory   We show that there are simplex pivoting rules for which it is PSPACE-complete
to tell if a particular basis will appear on the algorithm's path. Such rules
cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We
conjecture that the same can be shown for most known variants of the simplex
method. However, we also point out that Dantzig's shadow vertex algorithm has a
polynomial path problem. Finally, we discuss in the same context randomized
pivoting rules.

0
The categories of this paper are: hep-ph
35
The categories of this paper are: mtrl-th
28
The categories of this paper are: alg-geom
22
The categories of this paper are: chao-dyn
10
The categories of this paper are: q-bio
4
The categories of this paper are: cond-mat
19
The categories of this paper are: eess
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
27
The categories of this paper are: comp-gas
20
The categories of this paper are: acc-phys
36
The categories of this paper are: cmp-lg
12
The categories of this paper are: nucl-th
3
The categories of this paper are: physics
6
The categories of this paper are: astro-ph
16
The categories of this paper are: stat