1
$\begingroup$

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea of "NP mighty" algorithms (p3 def2). it follows a fruitful/continuing line of research analyzing P$\stackrel{?}{=}$NP wrt the simplex algorithm and linear programming of which there have been other major recent advances, eg results by Pokutta et al in [2] showing that the P-time TSP polytope must have an "unlikely/restrictive" form (commentaries in Barriers to P/NP proofs, RJLipton, also Stating P$\stackrel{?}{=}$NP without TMs). question (possibly with multiple leading answers):

the Disser/Skutella paper has closely related ideas but does not seem to explicitly reformulate the P$\stackrel{?}{=}$NP question. what is an equivalent way to state/study it in their introduced schema/framework of "NP Mighty" algorithms? what is a/the basic open problem in simplex/linear programming complexity theory that is equivalent to P$\stackrel{?}{=}$NP?

(somewhat related question: the Disser/Skutella paper also refers to Klee-Minty cubes, long used to show worst-case behavior on the simplex algorithm. are there any results relating lower bounds on them to general algorithmic lower bounds and/or complexity class separations eg P$\stackrel{?}{=}$NP etc?)

[1] "In defense of the Simplex Algorithm's worst-case behavior" Dissker/Skutella
[2] Exponential Lower Bounds for Polytopes in Combinatorial Optimization Fiorini et al

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ LP is in P, so all you would be able to do to talk about P = NP would be to prove that LP is NP-complete (this would imply P = NP). If you wanted to do that, you'd have to reduce integer programming to LP...which seems impossible (I tried it once). $\endgroup$
    – user1338
    Mar 7, 2014 at 16:40
  • $\begingroup$ the refs seem to imply there may be an answer not so simple as observing that "LP in P" and that integer programming is NP complete. forgot to mention: wrt the "NP mighty" defn an answer might be related to structure or restrictions on pivot rules. $\endgroup$
    – vzn
    Mar 8, 2014 at 17:01
  • 1
    $\begingroup$ You should explain the Disser/Skutella model. From a cursory read, they show that some standard variants of Simplex can be made to solve NP-hard problems "on the way" (the solution is in the trace of the algorithm). We know all these algorithms do have exponential worst case running time, but it may be meaningful to ask whether the running time is still exponential on the instances arising from NP-complete problems. Or if there is another poly-time algorithm that can compute states of one of these algorithms efficiently. $\endgroup$
    – Sasho Nikolov
    Mar 8, 2014 at 23:21
  • $\begingroup$ SN—thx yes more along the lines what was thinking. that leads somewhat to an idea of maybe studying the relationship of solving Klee-Minty cubes wrt NP hardness. $\endgroup$
    – vzn
    Mar 9, 2014 at 2:48

1 Answer 1

Reset to default
8
$\begingroup$

This answer is for your "somewhat related question":

In the following recent paper, Klee-Minty cubes were used explicitly to show that there exists a pivoting rule for the simplex method (not one of the standard ones, like Dantzig's pivoting rule analysed by Disser and Skutella) for which it is PSPACE-complete to decide whether a variable enters the basis for the simplex method with this pivoting rule. It was left open (Conjecture 3 in the paper) whether the same result holds for Dantzig's pivot rule.

I. Adler, C. Papadimitriou, and A. Rubinstein (2014). On Simplex Pivoting Rules and Complexity Theory. In Proc. of IPCO, pp. 13-24.

In the following paper we prove that conjecture and strengthen Disser and Skutella's result to show two PSPACE-completeness results for the simplex method with Dantzig's pivoting rule (one for whether a variable enters the basis "along the way" and another for whether a variable is in the final solution found by Dantzig's pivot rule).

J. Fearnley and R. Savani (2015). The Complexity of the Simplex Method. In Proc. of STOC, pp. 201-208. http://arxiv.org/abs/1404.0605

We use the known connection between linear programs and Markov decision processes (MDPs). A central part of our construction are the exponential-time examples due to Condon and Melekopoglou for single-switch policy iteration for MDPs. Those examples use a reflected binary Gray code, as used for Klee-Minty cubes. We use a modification of those examples as a clock to drive iterated circuit evaluation in our construction.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.