The encoding conjecture for convex-formulation languages
Let be the class of languages whose length- slices have convex hulls admitting extended formulations of polynomial size, and let be the subclass admitting such formulations with integral coefficients of polynomial encoding length.
Encoding conjecture.
The inclusion is immediate, while the reverse inclusion would say that every polynomial-size extended formulation can be replaced by one with polynomially bounded encoding length. The source presents this as an open conjecture; its significance is that it would identify the unrestricted and efficiently encodable classes of languages described by polynomial-size extended formulations.
References
Primary source
Thomas Rothvoß, “Some 0/1 polytopes need exponential size extended formulations”, arXiv:1105.0036 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.