Shared publicly  - 
 
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?
13
6
Francisco Pereira's profile photoJohn Moeller's profile photoFernando Pereira's profile photoDaniel Povey's profile photo
13 comments
 
Interesting article.
Are there any real-world problems where the time taken grows more than about linearly with the number of constraints?
 
It's a really good book, and it has tens of pages of interesting footnotes (not to detract from Cosma's erudition :). Thank you for the pointer to the seminar!
 
I meant that could be formulated as linear programs... [sorry, context was not obvious if you had not read the article].
 
More seriously, I would bet that the general answer to your question is "yes." Particularly since many real-world applications of LPs involve at least a few integer constraints, making them IPs or MIPs.
 
I had a look at the paper and I think there is some kind of caveat in there. From what I can see online, the TSP is NP-hard, and since LP is polynomially solvable, if this were true in the general case we'd have P=NP.
 
The missing observation is that it probably requires an exponential number of constraints. I only posted that jokingly.
 
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.
 
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.
 
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.
 
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]
 
+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."
Add a comment...