Stating P=NP Without Turing Machines(rjlipton.wordpress.com)
rjlipton.wordpress.com
Stating P=NP Without Turing Machines
http://rjlipton.wordpress.com/2010/06/26/stating-pnp-without-turing-machines/
8 comments
Does anyone know what the unsolved problems that Dantzig solved actually were?
Yes I found that myself, but it doesn't actually state what the problems were!
This is a great explanation. I found it really easy to follow.
The only part I'm having trouble understanding is the cubic graph example. I am aware of the four-color map theorem but I've never seen it expressed mathematically.
The only part I'm having trouble understanding is the cubic graph example. I am aware of the four-color map theorem but I've never seen it expressed mathematically.
> This is a great explanation. I found it really easy to follow.
I found it relatively easy to follow. But many of the technical details are either wrong or misleading.
I found it relatively easy to follow. But many of the technical details are either wrong or misleading.
Also, even if we proved P=NP wouldn't we still have to discover a general algorithm for solving IP systems?
We do have general algorithms for solving Linear Integer Programs. They just take some time, because IP is in NP. (It's also in Co-NP, if I remember correctly.)
If P=NP, and somebody has shown a polynomial algorithm for any one problem in NP [1], then we can construct a polynomial algorithm for IP.
Of course, getting a good polynomial algorithm for IP would still be an interesting problem. E.g. bubble sort is polynomial, but far from the ideal sorting algorithm for most applications.
We also have lots of algorithms to solve IP already, that work well in practise for many types of problems. But all of them become slower than polynomial for certain pathological inputs.
Interestingly, no polynomial simplex algorithm (for continuous linear programming) is known, but in practise simplex often performs faster than most polynomial algorithms for solving LP.
If P=NP, and somebody has shown a polynomial algorithm for any one problem in NP [1], then we can construct a polynomial algorithm for IP.
Of course, getting a good polynomial algorithm for IP would still be an interesting problem. E.g. bubble sort is polynomial, but far from the ideal sorting algorithm for most applications.
We also have lots of algorithms to solve IP already, that work well in practise for many types of problems. But all of them become slower than polynomial for certain pathological inputs.
Interestingly, no polynomial simplex algorithm (for continuous linear programming) is known, but in practise simplex often performs faster than most polynomial algorithms for solving LP.
http://news.ycombinator.org/item?id=1257488