The Klee-Minty cubes show that the simplex method is not in this class, while Khachian's ellipsoid method was the first example of a linear programming solution in this class.
Steve's class adds a spatial constraint to this class, and an open problem concerns whether Nick's class equals this class. The Klee-Minty cubes show that the simplex method is not in this class, while Khachian's ellipsoid method was the first example of a linear programming solution in this class. By Schaefer's dichotomy theorem, the Boolean satisfiability theorem for both Horn and anti-Horn formulas is in this class, and for any formula is either in this complexity class or in NP-complete. This complexity class contains problems that can be solved by a deterministic Turing machine. For 10 points, name this class of problems that can be solved in polynomial time, which may or may not equal NP.
Steve's class adds a spatial constraint to this class, and an open problem concerns whether Nick's class equals this class.
P [or early polynomial time]