{"id":252469,"date":"2022-08-21T21:22:27","date_gmt":"2022-08-21T21:22:27","guid":{"rendered":"https:\/\/mathewingram.com\/work\/?p=252469"},"modified":"2022-08-21T21:22:27","modified_gmt":"2022-08-21T21:22:27","slug":"so-is-p-equal-to-np-scientists-disagree","status":"publish","type":"post","link":"https:\/\/mathewingram.com\/work\/2022\/08\/21\/so-is-p-equal-to-np-scientists-disagree\/","title":{"rendered":"So is P equal to NP? Scientists disagree"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">From <a href=\"https:\/\/whyisthisinteresting.substack.com\/p\/the-p-vs-np-edition?utm_source=substack&amp;utm_medium=email&amp;utm_content=share&amp;action=share&amp;token=eyJ1c2VyX2lkIjoxMTQ0NDIsInBvc3RfaWQiOjQ2OTIzODQ3LCJpYXQiOjE2NDE4OTk0NzcsImlzcyI6InB1Yi03MDAwIiwic3ViIjoicG9zdC1yZWFjdGlvbiJ9.CXTCAwiu3jMLv_-YD0-LO3Yy0sjAvzH1PdvfBsJVPQs\">a recent edition of the great<\/a> &#8220;Why Is This Interesting&#8221; newsletter:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">P vs. NP is one of the great unsolved problems in cs\/math and is one of the seven Clay Institute Millenium Problems with a million-dollar bounty. To get that million, all you have to do is prove that there\u2019s a difference (or not) between problems that are easy for computers to solve (P) and those that are hard (NP). If that sounds a little crazy, it\u2019s because it is. Nearly every person working on P vs. NP believes that P is not the same as NP\u2014that there is some fundamental distinction between what is easy and hard for a computer to solve\u2014but to this point, no one has proven this is true.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Most things we ask a computer to do are relatively straightforward: sorting a list of words alphabetically, for example, can happen nearly instantaneously even if that list is 20,000 words long. These are called \u201cP\u201d problems because a regular computer can solve them in polynomial time. Polynomial-time is most easily understood as the number of elements you\u2019re processing\u2014say words in a list that need to be sorted\u2014raised to a fixed power like n^2 or n^5. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">On the other hand, some problems are more challenging for computers to solve: cryptographic techniques like finding prime factors, playing games like sudoku, solving math\/logic questions like the traveling salesman problem, and even finding the right configuration of packing boxes in your trunk, are all \u201chard\u201d in CS terms. In other words, we don\u2019t have an efficient algorithm to solve them.<\/p>\n\n\n<div class=\"syndication-links\"><\/div>","protected":false},"excerpt":{"rendered":"<p>From a recent edition of the great &#8220;Why Is This Interesting&#8221; newsletter: P vs. NP is one of the great unsolved problems in cs\/math and is one of the seven Clay Institute Millenium Problems with a million-dollar bounty. To get that million, all you have to do is prove that there\u2019s a difference (or not) &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/mathewingram.com\/work\/2022\/08\/21\/so-is-p-equal-to-np-scientists-disagree\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;So is P equal to NP? Scientists disagree&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crsspst_to_mathewingramblogwordpresscom":false,"mf2_syndication":[],"footnotes":"","jetpack_publicize_message":"","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},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-252469","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/posts\/252469","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/comments?post=252469"}],"version-history":[{"count":0,"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/posts\/252469\/revisions"}],"wp:attachment":[{"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/media?parent=252469"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/categories?post=252469"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathewingram.com\/work\/wp-json\/wp\/v2\/tags?post=252469"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}