Even by's impossibly erudite blogging standards, this is a tour de force. I've sometimes speculated over a drink about the mismatch between naive views of political economy and the computational limitations of planning and markets, but I'd never have the knowledge or skill to articulate the question in such a readable way, full of "must read" links and citations. How does he find the time?
In Soviet Union, Optimization Problem Solves You
Attention conservation notice: Over 7800 words about optimal planning for a socialist economy and its intersection with computational complexity theory. This is about as relevant to the world around us as debating whether a devotee of the Olypmian gods should approve of transgenic organisms. (Or: centaurs, yes or no?) Contains mathematical symbols but no actual math, and uses Red Plenty mostly as a launching point for a tangent. Cross-posted at ...
12 plus ones
Shared publicly•View activity
View 7 previous comments
- The missing observation is that it probably requires an exponential number of constraints. I only posted that jokingly.May 31, 2012
- I think their paper says it's polynomial.
I found a fun quote in the paper:
Computational complexity classes P and NP are equal."
So I think if mathematicians believed it were true, we'd have heard about it.May 31, 2012
- Don't confuse LPs and ILPs. The same set of constraints can be NP-hard as an ILP, but in P when relaxed to an LP.May 31, 2012
- The paper first reduces to an ILP and then claim that it can be reduced to a standard LP. And in the end they do explicitly claim that P = NP. But it's in some obscure engineering conference.May 31, 2012
- If someone has a smart student who is interested in LPs, they could ask them to try to find the mistake in the paper.
[I am both too under-qualified and too over-worked to do it myself]May 31, 2012
- : I think that you're taking that paper link way too seriously. It was just me being flippant. :-)
: I'm aware of the difference between IPs and LPs. I was trying to seriously answer the question "Are there any real-world problems where the time taken grows more than about linearly with the number of constraints?" The answer is "certainly," despite my TSP silliness.
However, if you want to be more specific and ask about pure LPs, then I don't know. However, I would still wager that the answer is "very probably."May 31, 2012