A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied I can recognize greatMessage 1 of 1 , Mar 24, 2005View Source
A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied "I can recognize great music but I can't create great music," the implication being that it's much harder to find a solution than to verify one.
But suppose NP-complete problems do have very efficient algorithms. Can we use them to create art, perhaps, as someone recently suggested to me, create a new Mozart opera, Shakespeare play or finish Schubert's symphony?
Perhaps we could use P=NP to find a small circuit that outputs "Shakespeare" plays. But these plays will only extrapolate from his known works. The program cannot add the new creative ideas Shakespeare puts in his works. It cannot create art just generate similar pieces.
Of course this whole exercise is moot since we strongly believe that NP-complete problems are hard. Even so a P=NP fantasyland might put some mathematicians and computer scientists out of work but true artists will still create in ways computers can never match.
Posted by Lance to Computational Complexity at 3/24/2005 05:43:00 AM