{"id":1948,"date":"2014-08-13T11:45:10","date_gmt":"2014-08-13T15:45:10","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1948"},"modified":"2017-01-12T18:19:32","modified_gmt":"2017-01-12T23:19:32","slug":"is-the-p-vs-np-problem-ill-posed-answer-no","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1948","title":{"rendered":"Is the P vs. NP problem ill-posed? (Answer: no.)"},"content":{"rendered":"

A couple days ago, a reader wrote to me to ask whether it’s possible that the solution to the P vs. NP problem is simply undefined—and that one should enlarge the space of possible answers using non-classical logics (the reader mentioned something called Catu\u1e63ko\u1e6di<\/span> logic<\/a>).\u00a0 Since other people have emailed me with similar questions in the past, I thought my response might be of more general interest, and decided to post it here.<\/p>\n

\n

Thanks for your mail! \u00a0I’m afraid I don’t agree with you that there’s a problem in the formulation of P vs. NP. \u00a0Let me come at it this way:<\/p>\n

Do you also think there might be a problem in the formulation of Goldbach’s Conjecture? \u00a0Or the Twin Prime Conjecture? \u00a0(I.e., that maybe the definition of “prime number” needs to be modified using\u00a0Catu\u1e63ko\u1e6di<\/span> logic?) \u00a0Or any other currently-unsolved problem in any other part of math?<\/p>\n

If you don’t, then my question would be: why single out P vs. NP?<\/p>\n

After all, P vs. NP can be expressed as a \u03a02<\/sub>-sentence: that is, as a certain relationship among positive integers, which either holds or doesn’t hold. \u00a0(In this case, the integers would encode Turing machines, polynomial upper bounds on their running time, and an NP-complete problem like 3SAT — all of which are expressible using the basic primitives of arithmetic.) \u00a0In terms of its logical form, then, it’s really no different than the Twin Prime Conjecture and so forth.<\/p>\n

So then, do you think that statements of arithmetic, like there being no prime number between 24 and 28, might also be like the Parallel Postulate? \u00a0That there might be some other, equally-valid “non-Euclidean arithmetic” where there is<\/em> a prime between 24 and 28?\u00a0 What exactly would one mean by that? \u00a0I understand exactly what one means by non-Euclidean geometries, but to my mind, geometry is less “fundamental” (at least in a logical sense) than positive integers are.\u00a0 And of course, even if one believes that non-Euclidean geometries are just as “fundamental” as Euclidean geometry — an argument that seems harder to make for, say, the positive integers versus the Gaussian integers or finite fields or p-adics\u00a0 — that still doesn’t change the fact that questions about Euclidean geometry have definite right answers.<\/p>\n

Let me acknowledge two important caveats to what I said:<\/p>\n

First, it’s certainly possible that P vs. NP might be independent<\/em> of standard formal systems like ZF set theory (i.e., neither provable nor disprovable in them). \u00a0That’s a possibility that everyone acknowledges, even if (like me) they consider it rather unlikely. \u00a0But note that, even if P vs. NP were independent of our standard formal systems, that still wouldn’t mean that the question was ill-posed! \u00a0There would still either be a Turing machine that decided 3SAT in polynomial time, or else there wouldn’t be. \u00a0It would “only” mean that the usual axioms of set theory wouldn’t suffice to tell us which.<\/p>\n

The second caveat is that P vs. NP, like any other mathematical question, can be generalized and extended in all sorts of interesting ways. \u00a0So for example, one can define analogues of P vs. NP over the reals and complex numbers (which are also<\/em> currently open, but which might be easier than the Boolean version). \u00a0Or, even if P\u2260NP, one can still ask if randomized algorithms, or nonuniform algorithms, or quantum algorithms, might be able to solve NP-complete problems in polynomial time. \u00a0Or one can ask whether NP-complete problems are at least efficiently solvable “on average,” if not in the worst case.\u00a0 Every one of these questions has been actively researched, and you could make a case that some of them are just as interesting as the original P vs. NP question, if not more<\/em> interesting — if history had turned out a little different, any one of these might have been what we’d taken as our “flagship” question, rather than P vs. NP. \u00a0But again, this still doesn’t change the fact that the original P vs. NP question has some definite answer (like, for example, P\u2260NP…), even if we can’t prove which answer it is, even if we won’t be able to prove it for 500 years.<\/p>\n

And please keep in mind that, if P vs. NP were solved after being open for hundreds of years, it would be far from the first such mathematical problem! \u00a0Fermat’s Last Theorem stayed open for 350 years, and the impossibility of squaring the circle and trisecting the angle were open for more than 2000 years. \u00a0Any time before these problems were solved, one could’ve said that maybe people had failed because the question itself was ill-posed, but one would’ve been mistaken. \u00a0People simply hadn’t invented the right ideas yet.<\/p>\n

Best regards,
\nScott<\/p>\n

\n

Unrelated Announcements:<\/b><\/span> As most of you have probably seen<\/a>, Subhash Khot won the Nevanlinna Prize, while Maryam Mirzakhani, Artur Avila, Manjul Bhargava and Martin Hairer won the Fields Medal. Mirzakhani is the first female Fields Medalist. Congratulations to all!<\/p>\n

Also, I join the rest of the world in saying that Robin Williams was a great actor—there was no one better at playing “the Robin Williams role” in any given movie—and his loss is a loss for humanity.<\/p>\n","protected":false},"excerpt":{"rendered":"

A couple days ago, a reader wrote to me to ask whether it’s possible that the solution to the P vs. NP problem is simply undefined—and that one should enlarge the space of possible answers using non-classical logics (the reader mentioned something called Catu\u1e63ko\u1e6di logic).\u00a0 Since other people have emailed me with similar questions in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5],"tags":[],"class_list":["post-1948","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1948","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1948"}],"version-history":[{"count":3,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1948\/revisions"}],"predecessor-version":[{"id":1952,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1948\/revisions\/1952"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1948"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1948"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1948"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}