3
$\begingroup$

I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his argument, despite having studied basic complexity theory. What is he talking about?

$\endgroup$
  • 1
    $\begingroup$ You're asking what somebody means without telling us what they actually said. Without some quotations, this question is essentially Chinese whispers. $\endgroup$ – David Richerby Jun 7 '15 at 8:07
  • $\begingroup$ I think Juho provided what I needed to understand. I will ask a different question after reading that. Thanks. $\endgroup$ – time Jun 7 '15 at 9:22
  • $\begingroup$ any proof that humans cant figure out implies limited human creativity. as for proof automation there is more thinking on this in the recent book by fortnow, Golden Ticket. there is an informal/ folklore idea that "finding proofs" might be easy if P=NP. but it seems this has not really been formalized. aaronson muses on P vs NP and not all of his ideas are mainstream esp because he is approaching it somewhat from a physicist angle. agreed, the exact quotes need to be considered. $\endgroup$ – vzn Jun 7 '15 at 15:40
3
$\begingroup$

There is a relatively often cited quote

"If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett."

However, Scott has later distanced from it:

Given how many confusions and weird misinterpretations it’s spawned, I, Scott Aaronson, hereby formally disown my statement about how “everyone who could appreciate a symphony would be Mozart” if P=NP.

(source)

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Here is a take on the idea in your question (trying not to put words in anyone's mouth). NP can be viewed as the class of statements that have "reasonable" proofs. Here statements are technically of the form "this string is in this language" and the proof is the "witness"/"certificate", and by "reasonable proof" I mean of polynomial size and verifiable in polynomial time.

P can be viewed as the subset of NP for which these proofs can be found efficiently and mechanically by an algorithm. If $\mathsf{P}=\mathsf{NP}$, then the algorithm removes the need for human creativity in finding the proof. If $\mathsf{P} \neq \mathsf{NP}$, then any algorithm would take a very long time and to get a fast proof of the statement, we need some heuristic like human creativity. In theory, anyway.

To make this viewpoint really bite, you'd want to connect the statements we want to actually prove to $\mathsf{NP}$ languages, which, like vzn, I haven't seen completely formalized. But I think the idea would be to consider a verifier that knows all of the axioms and rules of logic in your proof system and can check that each step in a given proof is an application of one of these axioms or logical rules to the previous step. Therefore, the language of interest is the set of true statements that can be deduced in your logic in $p(n)$ many steps, for a fixed polynomial $p(n)$. If $\mathsf{P}=\mathsf{NP}$, then there is an algorithm that checks if a given statement is in this language: given the statement we want to prove, it quickly and mechanically deduces whether it is true and provable in $p(n)$ steps.

It would be great if any experts could comment or improve this response....

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ think this is acceptable answer but lets keep in mind that certificates as "proofs" is a legitimate but very narrow/ specialized concept of proofs in math. $\endgroup$ – vzn Jun 8 '15 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.