<p>This answer is for your "somewhat related question":</p>

<p>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.  </p>

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

<p>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).</p>

<p>J. Fearnley and R. Savani (2015).
The Complexity of the Simplex Method. In Proc. of STOC, pp. 201-208. 
<a href="http://arxiv.org/abs/1404.0605" rel="nofollow noreferrer">http://arxiv.org/abs/1404.0605</a></p>

<p>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.</p>

CC BY-SA 3.0
2014-04-15T01:05:19.943Z
here is the arxiv link for the 1st ref: [On simplex pivoting rules and complexity theory](http://arxiv.org/abs/1404.3320) (Adler, Papadimitriou, Rubinstein) relating simplex pivoting rules to P=?Pspace etc
vzn
CC BY-SA 3.0
2014-04-06T06:02:57.727Z
2017-04-20T08:53:54.687Z
2017-04-20T08:53:54.687Z
Rahul Savani
<p>the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by <a href="https://cstheory.stackexchange.com/users/1846/saeed">saeed</a> on another interesting question. the paper introduces the idea of <em>"NP mighty" algorithms</em> (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 <a href="http://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/" rel="nofollow noreferrer">Barriers to P/NP proofs, RJLipton</a>, also <a href="http://rjlipton.wordpress.com/2010/06/26/stating-pnp-without-turing-machines/" rel="nofollow noreferrer">Stating P$\stackrel{?}{=}$NP without TMs</a>). question (possibly with multiple leading answers): </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>(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?)</p>

<p>[1] <a href="http://arxiv.org/abs/1311.5935" rel="nofollow noreferrer">"In defense of the Simplex Algorithm's worst-case behavior"</a> Dissker/Skutella<br>
[2] <a href="http://arxiv.org/abs/1111.0837" rel="nofollow noreferrer">Exponential Lower Bounds for Polytopes in Combinatorial Optimization</a> Fiorini et al</p>

CC BY-SA 3.0
2014-03-08T17:01:39.153Z
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
CC BY-SA 3.0
2014-03-08T23:21:12.420Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-03-09T02:48:44.923Z
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
<lower-bounds><linear-programming><p-vs-np><barriers><simplex>
equivalent way(s) of expressing P=?NP problem in linear programming?
vzn
# equivalent way(s) of expressing P=?NP problem in linear programming?

(Asked by: username_0 on 2014-03-07)

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](https://cstheory.stackexchange.com/users/1846/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](http://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/), also [Stating P$\stackrel{?}{=}$NP without TMs](http://rjlipton.wordpress.com/2010/06/26/stating-pnp-without-turing-machines/)). 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"](http://arxiv.org/abs/1311.5935) Dissker/Skutella  
[2] [Exponential Lower Bounds for Polytopes in Combinatorial Optimization](http://arxiv.org/abs/1111.0837) Fiorini et al

**Tags:** lower-bounds, linear-programming, p-vs-np, barriers, simplex

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-04-06. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: here is the arxiv link for the 1st ref: [On simplex pivoting rules and complexity theory](http://arxiv.org/abs/1404.3320) (Adler, Papadimitriou, Rubinstein) relating simplex pivoting rules to P=?Pspace etc  

---

