Even by +Cosma Shalizi'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?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:

"Theorem 6.

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 - +Daniel Povey: I think that you're taking that paper link way too seriously. It was just me being flippant. :-)

+Fernando Pereira: 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

Add a comment...