## Thursday, March 24, 2005

### P=NP and the Arts

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.

1. Probably because most people think NP is different from P, I don't think that anyone fully mapped out the practical consequences of, say, a linear-time SAT algorithm. I think that it's premature to say that artists, and even great artists, will be "safe" from being replaced by programs using such an algorithm.

Science is already pretty sure that artists, like all other human beings, can be emulated by a Boolean circuit of some large (but not inconceivable) size (e.g., 1000GB).
As far as my limited understanding goes, the main problem in simulating the brain using a computer is not its size but rather that this circuit was constructed using millions of years of evolution, and without NP=P, we don't know a shortcut to obtain its description faster.

Now, perhaps Shakespeare did not produce enough works for us to reconstruct his brain completely, but it may be that he did produce enough works for us to regenerate the "play generating" part that distinguishes him from other humans. I would certainly be very interested to see what would be the next output of the smallest circuit that can output all of Shakespeare's works.

Moreover, we could try to learn the circuit that Rudich (or anyone) uses to appreciate art, and use a SAT algorithm to find many objects that satisfy this circuit.

--Boaz

2. 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.

How do you distinguish between genuinely "new creative ideas" and "just similar pieces"? After all, the fact that some people can listen to a piece of music that they have never heard before and identify it (with reasonable success rate) as being by Beethoven simply based on "style" seems to suggest that even artists don't necessarily have new ideas (except possible the first time) but create similar pieces. I also seem to remember reading a news article some years ago about a program that "composed" some "Brahms" pieces which music critics
could not pick out as being fakes (though to be fair, when I googled this to try and find a reference, all I could find was
>this
which is not very convincing). So can there really be a non-subjective standard for whether a computer can produce "art"? Is there even such a standard for art produced by artists?

- Varsha

3. the fact that some people can listen to a piece of music that they have never heard before and identify it (with reasonable success rate) as being by Beethoven simply based on "style"

Once, there was this classical piece playing on the radio, and my train of thought over a minute or so was: "Nice.... likely Mozart..... quite nice... yes Mozart... nice, but oddly childish... not very ellaborately structured... childish..."

When the piece came to an end the announcer said: "that was a composition by Wolfang Amadeus Mozart, KV xxx, which he wrote when he was 5 years old".

"And here we are", I thought, "250 years later still listening to the compositions of such a prodigious 5 year old."

Alex Lopez-Ortiz

4. I think Varsh had the famous David Cope's Emmy program in mind. The page with some samples can be found here. This is about Douglas Hofstadter's (the author of "Goedel, Escher, Bach") reaction to Emmy. An excerpt from the above"
"Hofstadter offers his thoughts about Emmy in chapter 2. He feels amazed and even a bit fearful of Emmy because it seems capable of writing music that can touch his emotions just as strongly as music written by humans. He makes some of his argument in poetry: �Can one bypass the soul,/Can one sidestep all strife,/And produce wondrous music,/Without living a life?�"
Peter

5. Even granting the scientistic basis of Boaz's argument, one possible objection is that we are interested not so much in the artist's typical achievement as in his exceptional achievement. There are too few of those. We wouldn't really care if a computer could produce "Titus Andronicus"; "Measure for Measure" on the other hand...

6. There is some work on computer-assisted generation of poetry given today's tools. For example, see this review of the book _Virtual Muse_

http://www.altx.com/ebr/reviews/rev5/funk.htm

Most of the works I've seen are experiments with travesty generators or markov babblers as a stimulant for human creativity. I'm not aware, however, of any clearly specified decision problems that have come out of this work. (Put another way, we have no evidence as far as I know that "poetry is NP-hard.")

There have also been classical musicians interested in combinatorial approaches to composition. Here's a paper that applies some of their tools to analyze a piece by Ligeti
http://recherche.ircam.fr/equipes/repmus/RMPapers/Chemillier94/index.html

but there are also other composers that explicitly considered combinatorial approaches for composition (e.g. defining only subpieces of music and then inviting the players to compose them in any order). Again, I'm not aware of clearly specified problems here, but I expect that one could find an NP-hard problem without too much difficulty.

Of course, all this in some sense misses the point. We want to know if P=NP will help us capture human taste and produce novel "good works," not merely whether it will help produce more of a certain style...even if the style is something acknowledged to be good, such as Shakespeare.

Here learning theory seems like an appropriate tool, right? Given a bunch of examples of "good literature," output or at least predict a new piece of "good literature." Maybe attempting to apply a learning algorithm generated by a linear-time algorithm for SAT to this question would give us some indication as to which complexity class humans themselves fit. :)

--David Molnar

7. > We wouldn't really care if a
> computer could produce "Titus
> Andronicus"; "Measure for Measure"
> on the other hand...

It's like that Far Side cartoon, where a guy is screaming at his dog for doing such a shoddy lawnmowing job.

8. > I would certainly be very interested
> to see what would be the next output
> of the smallest circuit that can
> output all of Shakespeare's works.

I don't think this is sufficient. The smallest circuit that can output all of Shakespeare's works is probably the circuit that has each of his works hard-wired.

The circuit you want is almost surely larger -- it's the circuit that has some understanding of human emotion, language, etc. I doubt that something encoding all of this would be smaller than Shakespeare's text.

I realize my point is "nit-picky" in a sense, but it does annoy me a bit that the theory community makes such far-reaching claims about P vs. NP.

9. I think what Rudich says is
a nice criterion for art---something that is hard to produce
but easy to recognize. Complex in
form, but when studied everything makes sense and fits together naturally. If P=NP, then we could generate strings with this property in polynomial time. This is also related to the idea of "computational depth" (Antunes, Fortnow, van Melkebeek), deep strings being those hard to produce in time t but easy to produce in time s > t. If such strings are not "art", then,
at least they should provide some pleasure, after thinking for a bit, in discovering the simple description behind them.
--Troy

10. The circuit you want is almost surely larger -- it's the circuit that has some understanding of human emotion, language, etc. I doubt that something encoding all of this would be smaller than Shakespeare's text.Indeed, I meant that smallest circuit which can use the "human emulating" circuit (which understands emotion, language etc..) as oracle gates.

I agree that a linear-time algorithm for SAT does not make obtaining such a "human emulating" circuit trivial. Nor is it clear that it won't be possible to obtain such a circuit without such an algorithm.

However, because so many of the obstacles in understanding the brain, evolution, DNA etc.. are computational, and can be phrased as questions in NP or in the polynomial-hierarchy, I do believe that given a linear-time SAT algorithm, and using the things we already know about the brain, and technical advances that are already in the making, constructing the "human emulator" will be only a matter of a few decades.

Of course, like Lance said, this is most likely a moot point, since NP is probably not in P. (However, there are also interesting consequences if we manage to prove this, especially if we can get an explicit exponential or subexponential lower bound for interesting functions such as shortest-vector in a lattice, etc..)

I think that one theoretical result can never by itself change the world. However, as we saw in physics, one paper can, sometimes, make the cruicial step in a non-trivial process of changing the world.

11. Killer robots taking over the earth. Think about it, that's what P versus NP is all about. If P is equal to NP, then the robots can just use a passive bounded-mistake learning algorithm to learn how to kill many of us and turn the rest into slaves. Think about it.

Resolving P vs NP is an existential question about man's ability to outlive his creations.

Really, I don't know why the NSF is so hard on theory funding when such critical issues are at stake.

12. "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."

Why do you think that the human brain cannot be simulated fully by an algorithm?

13. Why do you think that the human brain cannot be simulated fully by an algorithm?

To simulate human brain (more or less) _fully_, you would have to model each neuron and each synapse. There are roughly 10^11 neurons and perhaps 10^14 synapses in the brain. The operating frequency (firing rate) is around 100Hz. Even disregarding all the complicated chemical stuff going on, each synapse would have to be modelled
by a system of PDE's. So you have a system of 10^14 coupled differential equations and you need enough precision to get 100 accurate data points per second.
Good luck.

14. Cool! I might be living in a fantasyland ;-)