{"id":966,"date":"2021-02-20T14:48:00","date_gmt":"2021-02-20T14:48:00","guid":{"rendered":"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/?p=966"},"modified":"2021-04-30T11:32:15","modified_gmt":"2021-04-30T11:32:15","slug":"the-p-vs-np-problem","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/the-p-vs-np-problem\/","title":{"rendered":"The P vs NP Problem"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In today’s blog post I want to give a very brief overview of a problem that is so important it features in the Clay Mathematical Institute’s “Millennium Problems<\/a>“, a list of problems that were considered the most important and challenging unsolved problems in the field of mathematics at the turn of the millennium.<\/p>

The problem I am going to touch upon today is the enticingly named the “P vs NP problem” (don’t worry the meaning of P and NP will be explained soon). This problem is probably the easiest for a non-mathematician to grasp and even solve if you happen to be minesweeper prodigy (more on this later). It also has great relevance to the field of operational research, so it was a natural choice for a blog post.<\/p>

Note: Saying that this problem has great relevance to operational research is putting things a bit lightly … more on this later in the post.<\/b><\/p>

The meaning behind P and NP<\/h3>

The crux of this problem is one of computational efficiency. It has stemmed from the desire of researchers to know how efficiently certain problems can be solved by supplying a computer with an algorithm (a set of instructions that will solve the problem for every possible input to that problem). An extremely simple example of an algorithm, and one that most of us are probably familiar with, is shown in the gif below. That’s right, the long multiplication technique that we all learned at school consists of a set of instructions for multiplying two n digit numbers that we could easily program into a computer to let it do the hard work for us. Taking a moment to think about how many steps we would expect this algorithm would take for two relatively small numbers can be quite illuminating. Essentially, we multiply each digit in one of the numbers by all the digits in the other. So for two five digit numbers we would end up multiplying 25 or \\( 5^{2} \\)\u00a0<\/i><\/span>digits together in 25 steps. There would also be some additional steps for carrying numbers and addition but the bulk of the steps involve these individual multiplications. In general we say that this algorithm is of order (of order just means that we look at the steps that contribute most) \\( n^{2} \\)<\/span>, where \\( n \\) is the number of digits in the numbers being multiplied.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"A\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Before defining <\/span>P<\/b><\/span> and <\/span>NP<\/b><\/span>, it is important to note that they are defined with respect to decision problems. A decision problem is just a problem in which the solution is a yes or no answer (i.e. does a solution exist?: Yes\/No).\u00a0 This isn’t really a limitation because most problems can be configured into decision problems with a bit of thought.<\/span><\/p>

\u00a0A decision problem is said to belong to the set of problems, <\/span>P<\/b><\/span>, if it has an algorithm associated with it that takes polynomial time. This means that if you have an input of size \\(\u00a0<\/span>n \\)<\/i>, the worst case running time of the algorithm is of order \\( n^{k} \\)\u00a0<\/span>, where\u00a0\\( k\u00a0 \\)\u00a0<\/i>is some constant. The multiplication algorithm given above is an example of a polynomial time algorithm that falls into class <\/span>P<\/b><\/span>.\u00a0 A look at the table below shows why this is an important consideration when trying to create an algorithm. As you can see, we have a range of different polynomial running times, expressed in terms of the input size \\( n \\), along with what kind of problem sizes we would expect to be able to solve on an average desktop computer and computers 100 and 1000 times faster than it. The main takeaway here is that a polynomial time algorithm, even when\u00a0<\/span>\\( k\u00a0 \\)\u00a0<\/i>is quite large (in practice, most algorithms in <\/span>P<\/b><\/span> have<\/span>\u00a0\\( k \u2264 4 \\)), has the scope to be applied to problems with large n and that n will increase appreciably with an increase in computing power. Note too that increases in computing power of these sizes is very realistic, especially if an algorithm can be designed to run on many computers at once. The second takeaway is in the final row which shows a common running time for an algorithm not in <\/span>P<\/b><\/span>. You can see why algorithms that do not belong to <\/span>P<\/b><\/span> are generally considered unusable for large problem instances. Using 1000 times the computing power results in only being able to compute an input size that has approximately 10 additional inputs. This is a shocking result!<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"TableCompComplex\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

So, what does NP<\/b> mean? NP<\/b> stands for Non-deterministic Polynomial time and is a set of problems that do not have a algorithm that can find a solution in polynomial time. However, if you have a solution, there are algorithms that can check if that solution is correct in polynomial time. An example of a problem that is in the set NP<\/b> is shown below. It is the problem of trying to find out whether a Hamiltonian cycle exists for a given connected graph of vertices. A Hamiltonian cycle is the name given to a path taken around the graph that visits every vertex once before returning to the start. It is shown in red on the graph below. It turns out that there isn’t an algorithm that we know of that works out whether a given graph has a Hamiltonian cycle that takes polynomial time. On the other hand, if we are given a graph with a Hamiltonian cycle, it is a fairly trivial matter of checking if it is a true Hamiltonian cycle and we have a polynomial time algorithm to do so.\u00a0\u00a0<\/span>A quick note here that all problems in the set<\/span> P<\/b><\/span> belong to the set <\/span>NP<\/b><\/span> as solving a problem in polynomial time means that by extension we can check it in polynomial time.\u00a0<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\"1024px\t\t\t\t\t\t\t\t\t\t\t
Christoph Sommer, CC BY-SA 3.0 , via Wikimedia Commons<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

There is a subset of problems that belong to the set <\/span>NP<\/b><\/span> that have a property known as <\/span>NP-completeness<\/b><\/span>. A problem is said to be <\/span>NP-complete<\/b><\/span> if all of the other problems in <\/span>NP<\/b><\/span> can be transformed into it in polynomial time. I won’t go into great detail about the concept of transforming a problem here but it essentially involves adding extra features to a problem so that by solving it you solve a different problem. Transforming in polynomial time just means that any steps involved in the transformation take polynomial time.<\/span> NP-completeness<\/b><\/span> is a compelling thing because if we could discover a polynomial time algorithm for an<\/span> NP-complete <\/b><\/span>problem them we would have a polynomial time algorithm we could apply to every problem in <\/span>NP<\/b><\/span>.<\/span><\/p>\n

It turns out that a lot of important problems in many important fields belong to the set <\/span>NP<\/b><\/span>, an example being the travelling salesman problem in operational research. The “<\/span>P vs NP<\/b><\/span> problem” is the problem that we don’t kn<\/span>ow whether  the fact that we do not have polynomial time algorithms for <\/span>NP<\/b><\/span> problems is due to a lack of human inventiveness or due to the fact that there will never be a polynomial time algorithm for <\/span>NP<\/b><\/span> problems. Most researchers currently believe that<\/span> P \u2260 NP <\/b><\/span>but it would be necessary to produce a rigorous mathematical proof of this to put the <\/span>P vs NP<\/b><\/span> problem to rest. This is not a straightforward task at all, how do you go about showing that there will never be a method that can be used to solve any <\/span>NP<\/b><\/span>-complete problem in polynomial time. In fact, there is research that shows that current methods of obtaining mathematical proofs are not powerful enough to prove <\/span>P \u2260 NP<\/b><\/span>.<\/span><\/p>\n

 On the other hand, there is the enticing possibility that <\/span>P = NP<\/b><\/span>. In theory, this is a much easier thing to prove because it would require the creation of a polynomial time algorithm for one of the many thousands of <\/span>NP-complete<\/b><\/span> problems. This is where minesweeper comes in, it turns out that minesweeper has been proven to be an <\/span>NP-complete<\/b><\/span> problem and therefore if you were to able to come up with an algorithm that solves a minesweeper grid of size \\( n \\) in time \\( n^k \\), you will have proved that <\/span>P = NP<\/b><\/span>. The hilarious conclusion to this would be that it would turn out that the best way to solve serious operational research problems such as integer programming and travelling salesman would be to convert them into a game of minesweeper. <\/span><\/p>\n

I think that sums up the consequences of a proof that <\/span>P = NP<\/b><\/span>. It would be completely insane and world altering. Suddenly we would be able to solve incredibly complicated problems that we could have only dreamed of solving before such as protein folding and cryptography and that’s just thinking of immediate and somewhat narrow minded consequences. Not all problems belong to just the sets <\/span>P<\/b><\/span> and <\/span>NP<\/b><\/span> however, there are other problems such as deciding if a chess move is the best possible move that take non-polynomial time to even evaluate whether a given solution is the best move (you essentially have to play every possible continuation to the chess game after that move). A proof of<\/span> P = NP<\/b><\/span> would not mean that we could easily solve every possible problem.<\/span><\/p>\n

A proof that <\/span>P \u2260 NP<\/b><\/span> would certainly be a bit more mundane but it would still put the problem to rest and allow researchers to completely focus on alternative heuristic solutions to <\/span>NP<\/b><\/span> problems which attempt to give good solutions in most but not all cases of the problem. In fact, the fruitlessness of the search for polynomial time algorithms for <\/span>NP<\/b><\/span> problems means that this shift in research focus has already begun to happen but there are still many who have not given up hope of finding that elusive algorithm just yet …<\/span><\/p>\n

Relevant Links<\/span><\/p>\n

Statement of the P vs NP problem<\/a><\/p>\n

Minesweeper is NP complete<\/a><\/p>\n

Proposed (and debunked) proofs <\/a><\/p>\n

\n<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

In today’s blog post I want to give a very brief overview of a problem that is so important it features in the Clay Mathematical Institute’s “Millennium Problems“, a list of problems that were considered the most important and challenging unsolved problems in the field of mathematics at the turn of the millennium. The problem […]<\/p>\n","protected":false},"author":19,"featured_media":1073,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"slim_seo":{"title":"The P vs NP Problem - JACK TRAINER","description":"In today's blog post I want to give a very brief overview of a problem that is so important it features in the Clay Mathematical Institute's \" Millennium Proble"},"footnotes":""},"categories":[14],"tags":[19,17,20,18],"class_list":["post-966","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science","tag-algorithms","tag-computer-science","tag-millennium-problem","tag-programming"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/966","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/users\/19"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/comments?post=966"}],"version-history":[{"count":50,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/966\/revisions"}],"predecessor-version":[{"id":1178,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/966\/revisions\/1178"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/media\/1073"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/media?parent=966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/categories?post=966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/tags?post=966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}