# equivalent way(s) of expressing P=?NP problem in linear programming?

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

• 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). Mar 7 '14 at 16:40
• 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.
– vzn
Mar 8 '14 at 17:01
• 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. Mar 8 '14 at 23:21
• 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.
– vzn
Mar 9 '14 at 2:48