News for hackers. Stuff that matters.
Re:P ≠ NP by jacoblyles on Sunday August 08, 2010 @05:52PM (#1586280)
I didn't follow everything in my complexity class, but I believe that P=NP implies that search is as easy as decision. So producing a piece of good music is as easy (up to a polynomial) as deciding if a piece of music is good.

If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.

Re:P ≠ NP by nandemo on Sunday August 08, 2010 @11:47PM (#1586937)
Up to a polynomial.

What if the polynomial is of order 1000 or higher?

I understand asymptotics and the convention that polynomial algorithms are "efficient". However, it might turn out that P=NP but the polynomial is so big that the found algorithm is impractical for normal sized instances.

Re:P ≠ NP by jacoblyles on Monday August 09, 2010 @05:25PM (#1589454)
That's certainly a logical possibility. In practice, low-degree polynomial solutions have been developed for most important problems in P, even if the first known polynomial solution had a high degree.
Re:P ≠ NP by eru on Monday August 09, 2010 @06:23PM (#1589644)
What would be even more entertaining, is a non-constructive proof of NP=P.