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
equivalent way(s) of expressing P=?NP problem in linear programming?
lower bounds;linear programming;p vs np;barriers;simplex
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.0605We 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.