What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:22:10Z https://cs.stackexchange.com/feeds/question/9556 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/9556 245 What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? agent154 https://cs.stackexchange.com/users/6569 2013-02-06T20:38:08Z 2019-08-14T22:05:29Z <p>I'm in a course about <em>computing</em> and <em>complexity</em>, and am unable to understand what these terms mean. </p> <p>All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea what they actually mean. <a href="https://en.wikipedia.org/wiki/Complexity_class" rel="noreferrer">Wikipedia</a> isn't much help either, as the explanations are still a bit too high level.</p> https://cs.stackexchange.com/questions/9556/-/9557#9557 7 Answer by Pål GD for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? Pål GD https://cs.stackexchange.com/users/4249 2013-02-06T21:13:13Z 2013-02-06T21:13:13Z <p>Simplest of them is P, problems solvable in polynomial time belongs here.</p> <p>Then comes NP. Problems solvable in polynomial time on a non-deterministic Turing machine belongs here.</p> <p>The hardness and completeness has to with reductions. A problem A is <em>hard</em> for a class C if every problem in C reduces to A. If problem A is <em>hard for NP</em>, or NP-hard, if every problem in NP reduces to A.</p> <p>Finally, a problem is <em>complete</em> for a class C if it is <em>in</em> C and <em>hard</em> for C. In your case, problem A is <em>complete for NP</em>, or NP-complete, if every problem in NP reduces to A, and A is in NP.</p> <p>To add to explanation of NP, a problem is in NP if and only if a solution can be verified in (deterministic) polynomial time. Consider any NP-complete problem you know, SAT, CLIQUE, SUBSET SUM, VERTEX COVER, etc. If you "get the solution", you can verify its correctness in polynomial time. They are, resp., truth assignments for variables, complete subgraph, subset of numbers and set of vertices that dominates all edges.</p> https://cs.stackexchange.com/questions/9556/-/9560#9560 26 Answer by Reza for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? Reza https://cs.stackexchange.com/users/6550 2013-02-06T21:56:42Z 2013-02-06T21:56:42Z <p>More than useful mentioned answers, I recommend you <strong>highly</strong> to watch "<a href="https://www.youtube.com/watch?v=msp2y_Y5MLE"><strong>Beyond Computation: The P vs NP Problem</strong></a>" by <strong><a href="http://en.wikipedia.org/wiki/Michael_Sipser">Michael Sipser</a></strong>. I think this video should be archived as one of the leading teaching video in computer science.!</p> <p>Enjoy! </p> https://cs.stackexchange.com/questions/9556/-/9566#9566 358 Answer by Kaveh for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? Kaveh https://cs.stackexchange.com/users/41 2013-02-07T04:00:47Z 2019-04-23T13:35:11Z <p>I think the Wikipedia articles <a href="http://en.wikipedia.org/wiki/P_%28complexity%29" rel="noreferrer"><span class="math-container">$\mathsf{P}$</span></a>, <a href="http://en.wikipedia.org/wiki/NP_%28complexity%29" rel="noreferrer"><span class="math-container">$\mathsf{NP}$</span></a>, and <a href="http://en.wikipedia.org/wiki/P_versus_NP_problem" rel="noreferrer"><span class="math-container">$\mathsf{P}$</span> vs. <span class="math-container">$\mathsf{NP}$</span></a> are quite good. Still here is what I would say: <a href="https://cs.stackexchange.com/a/9566/41">Part I</a>, <a href="https://cs.stackexchange.com/a/18666/41">Part II</a></p> <p>[I will use remarks inside brackets to discuss some technical details which you can skip if you want.]</p> <hr> <h1>Part I</h1> <h3>Decision Problems</h3> <p>There are various kinds of computational problems. However in an introduction to computational complexity theory course it is easier to focus on <strong>decision problem</strong>, i.e. problems where the answer is either YES or NO. There are other kinds of computational problems but most of the time questions about them can be reduced to similar questions about decision problems. Moreover decision problems are very simple. Therefore in an introduction to computational complexity theory course we focus our attention to the study of decision problems.</p> <p>We can identify a decision problem with the subset of inputs that have answer YES. This simplifies notation and allows us to write <span class="math-container">$x\in Q$</span> in place of <span class="math-container">$Q(x)=YES$</span> and <span class="math-container">$x \notin Q$</span> in place of <span class="math-container">$Q(x)=NO$</span>.</p> <p>Another perspective is that we are talking about <strong>membership queries</strong> in a set. Here is an example:</p> <p><strong>Decision Problem:</strong> </p> <blockquote> <p>Input: A natural number <span class="math-container">$x$</span>,<br> Question: Is <span class="math-container">$x$</span> an even number?</p> </blockquote> <p><strong>Membership Problem:</strong></p> <blockquote> <p>Input: A natural number <span class="math-container">$x$</span>,<br> Question: Is <span class="math-container">$x$</span> in <span class="math-container">$Even = \{0,2,4,6,\cdots\}$</span>?</p> </blockquote> <p>We refer to the YES answer on an input as <strong>accepting</strong> the input and to the NO answer on an input as <strong>rejecting</strong> the input.</p> <p>We will look at <strong>algorithms</strong> for decision problems and discuss how efficient those algorithms are in their <em>usage of <strong>computable resources</strong></em>. I will rely on your intuition from programming in a language like C in place of formally defining what we mean by an algorithm and computational resources.</p> <p>[Remarks: 1. If we wanted to do everything formally and precisely we would need to fix a model of computation like the standard <a href="https://en.wikipedia.org/wiki/Turing_machine" rel="noreferrer">Turing machine</a> model to <em>precisely</em> define what we mean by an algorithm and its usage of computational resources. 2. If we want to talk about computation over objects that the model cannot directly handle, we would need to encode them as objects that the machine model can handle, e.g. if we are using Turing machines we need to encode objects like natural numbers and graphs as binary strings.]</p> <hr> <h3><span class="math-container">$\mathsf{P}$</span> = Problems with Efficient Algorithms for <em>Finding</em> Solutions</h3> <p>Assume that <strong>efficient algorithms</strong> means algorithms that use at most <strong>polynomial</strong> amount of computational resources. The main resource we care about is the worst-case <strong>running time</strong> of algorithms with respect to the input size, i.e. the number of basic steps an algorithm takes on an input of size <span class="math-container">$n$</span>. The size of an input <span class="math-container">$x$</span> is <span class="math-container">$n$</span> if it takes <span class="math-container">$n$</span>-bits of computer memory to store <span class="math-container">$x$</span>, in which case we write <span class="math-container">$|x| = n$</span>. So <em>by efficient algorithms we mean algorithms that have polynomial worst-case running time</em>.</p> <p>The <em>assumption</em> that polynomial-time algorithms capture the intuitive notion of efficient algorithms is known as <a href="http://en.wikipedia.org/wiki/Cobham%27s_thesis" rel="noreferrer">Cobham's thesis</a>. I will not discuss at this point whether <span class="math-container">$\mathsf{P}$</span> is the right model for efficiently solvable problems and whether <span class="math-container">$\mathsf{P}$</span> does or does not capture what can be computed efficiently in practice and related issues. For now there are good reasons to make this assumption so for our purpose we assume this is the case. If you do not accept Cobham's thesis it does not make what I write below incorrect, the only thing we will lose is the <em>intuition</em> about efficient computation in practice. I think it is a helpful assumption for someone who is starting to learn about complexity theory.</p> <blockquote> <p><strong><span class="math-container">$\mathsf{P}$</span> is the class of decision problems that can be solved efficiently</strong>,<br> i.e. decision problems which have polynomial-time algorithms.</p> </blockquote> <p>More formally, we say a decision problem <span class="math-container">$Q$</span> is in <span class="math-container">$\mathsf{P}$</span> iff</p> <blockquote> <p>there is an efficient algorithm <span class="math-container">$A$</span> such that<br> for all inputs <span class="math-container">$x$</span>, </p> <ul> <li>if <span class="math-container">$Q(x)=YES$</span> then <span class="math-container">$A(x)=YES$</span>, </li> <li>if <span class="math-container">$Q(x)=NO$</span> then <span class="math-container">$A(x)=NO$</span>.</li> </ul> </blockquote> <p>I can simply write <span class="math-container">$A(x)=Q(x)$</span> but I write it this way so we can compare it to the definition of <span class="math-container">$\mathsf{NP}$</span>.</p> <hr> <h3><span class="math-container">$\mathsf{NP}$</span> = Problems with Efficient Algorithms for <em>Verifying</em> Proofs/Certificates/Witnesses</h3> <p>Sometimes we do not know any efficient way of finding the answer to a decision problem, however if someone tells us the answer and gives us a <strong>proof</strong> we can efficiently <strong>verify</strong> that the answer is correct by checking the proof to see if it is a <strong>valid proof</strong>. This is the idea behind the complexity class <span class="math-container">$\mathsf{NP}$</span>.</p> <p>If the proof is too long it is not really useful, it can take too long to just read the proof let alone check if it is valid. We want the time required for verification to be reasonable in the size of the original input, not the size of the given proof! This means what we really want is not arbitrary long proofs but <em>short</em> proofs. Note that if the verifier's running time is polynomial in the size of the original input then it can only read a polynomial part of the proof. So by <em>short</em> we mean <em>of polynomial size</em>.</p> <p>Form this point on whenever I use the word "proof" I mean "short proof".</p> <p>Here is an example of a problem which we <em>do not know</em> how to solve efficiently but we can efficiently verify proofs:</p> <blockquote> <p><strong>Partition</strong><br> <strong>Input:</strong> a finite set of natural numbers <span class="math-container">$S$</span>,<br> <strong>Question:</strong> is it possible to partition <span class="math-container">$S$</span> into two sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span> (<span class="math-container">$A \cup B = S$</span> and <span class="math-container">$A \cap B = \emptyset$</span>)<br> such that the sum of the numbers in <span class="math-container">$A$</span> is equal to the sum of number in <span class="math-container">$B$</span> (<span class="math-container">$\sum_{x\in A}x=\sum_{x\in B}x$</span>)?</p> </blockquote> <p>If I give you <span class="math-container">$S$</span> and ask you if we can partition it into two sets such that their sums are equal, you do not know any efficient algorithm to solve it. You will probably try all possible ways of partitioning the numbers into two sets until you find a partition where the sums are equal or until you have tried all possible partitions and none has worked. If any of them worked you would say YES, otherwise you would say NO. </p> <p>But there are <em>exponentially</em> many possible partitions so it will take a lot of time. However if <em>I give you</em> two sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, you can easily check if the sums are equal and if <span class="math-container">$A$</span> and <span class="math-container">$B$</span> is a partition of <span class="math-container">$S$</span>. Note that we can compute sums efficiently. </p> <p>Here the pair of <span class="math-container">$A$</span> and <span class="math-container">$B$</span> that I give you is a proof for a YES answer. You can efficiently verify my claim by looking at my proof and checking if it is a <strong>valid proof</strong>. If the answer is YES then there is a valid proof, and I can give it to you and you can verify it efficiently. If the answer is NO then there is no valid proof. So whatever I give you you can check and see it is not a valid proof. I cannot trick you by an invalid proof that the answer is YES. Recall that if the proof is too big it will take a lot of time to verify it, we do not want this to happen, so we only care about <em>efficient</em> proofs, i.e. proofs which have polynomial size.</p> <p>Sometimes people use "<strong>certificate</strong>" or "<strong>witness</strong>" in place of "proof". </p> <p>Note I am giving you enough information about the answer for a given input <span class="math-container">$x$</span> so that you can find and verify the answer efficiently. For example, in our partition example I do not tell you the answer, I just give you a partition, and you can check if it is valid or not. Note that you have to verify the answer yourself, you cannot trust me about what I say. Moreover you can only check the correctness of <em>my</em> proof. If my proof is valid it means the answer is YES. But if my proof is invalid it does <em>not</em> mean the answer is NO. You have seen that one proof was invalid, not that there are no valid proofs. We are talking about proofs for YES. We are not talking about proofs for NO.</p> <p>Let us look at an example: <span class="math-container">$A=\{2,4\}$</span> and <span class="math-container">$B=\{1,5\}$</span> is a proof that <span class="math-container">$S=\{1,2,4,5\}$</span> can be partitioned into two sets with equal sums. We just need to sum up the numbers in <span class="math-container">$A$</span> and the numbers in <span class="math-container">$B$</span> and see if the results are equal, and check if <span class="math-container">$A$</span>, <span class="math-container">$B$</span> is partition of <span class="math-container">$S$</span>.</p> <p>If I gave you <span class="math-container">$A=\{2,5\}$</span> and <span class="math-container">$B=\{1,4\}$</span>, you will check and see that my proof is invalid. It does not mean the answer is NO, it just means that this particular proof was invalid. Your task here is <em>not</em> to find the answer, but only to check if the proof you are given is valid. </p> <p>It is like a student solving a question in an exam and a professor checking if the answer is correct. :) (unfortunately often students do not give enough information to verify the correctness of their answer and the professors have to guess the rest of their partial answer and decide how much mark they should give to the students for their partial answers, indeed a quite difficult task).</p> <p>The amazing thing is that the same situation applies to many other natural problems that we want to solve: <strong>we can efficiently <em>verify</em> if a given short proof is valid, but we do not know any efficient way of <em>finding</em> the answer</strong>. This is the motivation why the complexity class <span class="math-container">$\mathsf{NP}$</span> is <em>extremely interesting</em> (though this was not the original motivation for defining it). Whatever you do (not just in CS, but also in math, biology, physics, chemistry, economics, management, sociology, business, ...) you will face computational problems that fall in this class. To get an idea of how many problems turn out to be in <span class="math-container">$\mathsf{NP}$</span> check out <a href="http://www.nada.kth.se/~viggo/wwwcompendium/" rel="noreferrer">a compendium of NP optimization problems</a>. Indeed you will have hard time finding natural problems which are not in <span class="math-container">$\mathsf{NP}$</span>. It is simply amazing.</p> <blockquote> <p><strong><span class="math-container">$\mathsf{NP}$</span> is the class of problems which have efficient verifiers</strong>, i.e.<br> there is a polynomial time algorithm that can verify if a given solution is correct. </p> </blockquote> <p>More formally, we say a decision problem <span class="math-container">$Q$</span> is in <span class="math-container">$\mathsf{NP}$</span> iff</p> <blockquote> <p>there is an efficient algorithm <span class="math-container">$V$</span> called verifier such that<br> for all inputs <span class="math-container">$x$</span>, </p> <ul> <li>if <span class="math-container">$Q(x)=YES$</span> then there is a proof <span class="math-container">$y$</span> such that <span class="math-container">$V(x,y)=YES$</span>,</li> <li>if <span class="math-container">$Q(x)=NO$</span> then for all proofs <span class="math-container">$y$</span>, <span class="math-container">$V(x,y)=NO$</span>.</li> </ul> </blockquote> <p>We say a verifier is <strong>sound</strong> if it does not accept any proof when the answer is NO. In other words, a sound verifier cannot be tricked to accept a proof if the answer is really NO. No false positives.</p> <p>Similarly, we say a verifier is <strong>complete</strong> if it accepts at least one proof when the answer is YES. In other words, a complete verifier can be convinced of the answer being YES.</p> <p>The terminology comes from logic and <strong>proof systems</strong>. We cannot use a sound proof system to prove any false statements. We can use a complete proof system to prove all true statements.</p> <p>The verifier <span class="math-container">$V$</span> gets two inputs, </p> <ul> <li><span class="math-container">$x$</span> : the original input for <span class="math-container">$Q$</span>, and </li> <li><span class="math-container">$y$</span> : a suggested proof for <span class="math-container">$Q(x)=YES$</span>.</li> </ul> <p>Note that we want <span class="math-container">$V$</span> to be efficient in the size of <span class="math-container">$x$</span>. If <span class="math-container">$y$</span> is a big proof the verifier will be able to read <em>only a polynomial part</em> of <span class="math-container">$y$</span>. That is why we require the proofs to be short. If <span class="math-container">$y$</span> is short saying that <span class="math-container">$V$</span> is efficient in <span class="math-container">$x$</span> is the same as saying that <span class="math-container">$V$</span> is efficient in <span class="math-container">$x$</span> and <span class="math-container">$y$</span> (because the size of <span class="math-container">$y$</span> is bounded by a fixed polynomial in the size of <span class="math-container">$x$</span>).</p> <p>In summary, to show that a decision problem <span class="math-container">$Q$</span> is in <span class="math-container">$\mathsf{NP}$</span> we have to give an <em>efficient</em> verifier algorithm which is <em>sound</em> and <em>complete</em>.</p> <p>Historical Note: historically this is not the original definition of <span class="math-container">$\mathsf{NP}$</span>. The original definition uses what is called <strong>non-deterministic</strong> Turing machines. These machines do not correspond to any <em>actual</em> machine model and are difficult to get used to (at least when you are starting to learn about complexity theory). I have read that many experts think that they would have used the verifier definition as the main definition and even would have named the class <span class="math-container">$\mathsf{VP}$</span> (for verifiable in polynomial-time) in place of <span class="math-container">$\mathsf{NP}$</span> if they go back to the dawn of the computational complexity theory. The verifier definition is more natural, easier to understand conceptually, and easier to use to show problems are in <span class="math-container">$\mathsf{NP}$</span>.</p> <hr> <h3><span class="math-container">$\mathsf{P}\subseteq \mathsf{NP}$</span></h3> <p>Therefore we have <strong><span class="math-container">$\mathsf{P}$</span>=efficient solvable</strong> and <strong><span class="math-container">$\mathsf{NP}$</span>=efficiently verifiable</strong>. So <span class="math-container">$\mathsf{P}=\mathsf{NP}$</span> iff the problems that can be efficiently verified are the same as the problems that can be efficiently solved.</p> <p>Note that any problem in <span class="math-container">$\mathsf{P}$</span> is also in <span class="math-container">$\mathsf{NP}$</span>, i.e. if you can solve the problem you can also verify if a given proof is correct: the verifier will just ignore the proof! </p> <p>That is because we do not need it, the verifier can compute the answer by itself, it can decide if the answer is YES or NO without any help. If the answer is NO we know there should be no proofs and our verifier will just reject every suggested proof. If the answer is YES, there should be <em>a</em> proof, and in fact we will just accept anything as a proof.</p> <p>[We could have made our verifier accept only some of them, that is also fine, as long as our verifier accept at least one proof the verifier works correctly for the problem.]</p> <p>Here is an example: </p> <blockquote> <p><strong>Sum</strong><br> <strong>Input:</strong> a list of <span class="math-container">$n+1$</span> natural numbers <span class="math-container">$a_1,\cdots,a_n$</span>, and <span class="math-container">$s$</span>,<br> <strong>Question:</strong> is <span class="math-container">$\Sigma_{i=1}^n a_i = s$</span>?</p> </blockquote> <p>The problem is in <span class="math-container">$\mathsf{P}$</span> because we can sum up the numbers and then compare it with <span class="math-container">$s$</span>, we return YES if they are equal, and NO if they are not.</p> <p>The problem is also in <span class="math-container">$\mathsf{NP}$</span>. Consider a verifier <span class="math-container">$V$</span> that gets a proof plus the input for Sum. It acts the same way as the algorithm in <span class="math-container">$\mathsf{P}$</span> that we described above. This is an efficient verifier for Sum.</p> <p>Note that there are other efficient verifiers for Sum, and some of them might use the proof given to them. However the one we designed does not and that is also fine. Since we gave an efficient verifier for Sum the problem is in <span class="math-container">$\mathsf{NP}$</span>. The same trick works for all other problems in <span class="math-container">$\mathsf{P}$</span> so <span class="math-container">$\mathsf{P} \subseteq \mathsf{NP}$</span>.</p> <hr> <h3>Brute-Force/Exhaustive-Search Algorithms for <span class="math-container">$\mathsf{NP}$</span> and <span class="math-container">$\mathsf{NP}\subseteq \mathsf{ExpTime}$</span></h3> <p>The best algorithms <em>we know of</em> for solving an arbitrary problem in <span class="math-container">$\mathsf{NP}$</span> are <em>brute-force</em>/<em>exhaustive-search</em> algorithms. Pick an efficient verifier for the problem (it has an efficient verifier by our assumption that it is in <span class="math-container">$\mathsf{NP}$</span>) and check all possible proofs one by one. If the verifier accepts one of them then the answer is YES. Otherwise the answer is NO. </p> <p>In our partition example, we try all possible partitions and check if the sums are equal in any of them.</p> <p>Note that the brute-force algorithm runs in worst-case exponential time. The size of the proofs is polynomial in the size of input. If the size of the proofs is <span class="math-container">$m$</span> then there are <span class="math-container">$2^m$</span> possible proofs. Checking each of them will take polynomial time by the verifier. So in total the brute-force algorithm takes exponential time.</p> <p>This shows that any <span class="math-container">$\mathsf{NP}$</span> problem can be solved in exponential time, i.e. <span class="math-container">$\mathsf{NP}\subseteq \mathsf{ExpTime}$</span>. (Moreover the brute-force algorithm will use only a polynomial amount of space, i.e. <span class="math-container">$\mathsf{NP}\subseteq \mathsf{PSpace}$</span> but that is a story for another day). </p> <p>A problem in <span class="math-container">$\mathsf{NP}$</span> can have much faster algorithms, for example any problem in <span class="math-container">$\mathsf{P}$</span> has a polynomial-time algorithm. However for an arbitrary problem in <span class="math-container">$\mathsf{NP}$</span> we do not know algorithms that can do much better. In other words, if you just tell me that your problem is in <span class="math-container">$\mathsf{NP}$</span> (and nothing else about the problem) then the fastest algorithm that we know of for solving it takes exponential time.</p> <p>However it does not mean that there are not any better algorithms, <em>we do not know that</em>. As far as we know it is still possible (though thought to be very unlikely by almost all complexity theorists) that <span class="math-container">$\mathsf{NP}=\mathsf{P}$</span> and all <span class="math-container">$\mathsf{NP}$</span> problems can be solved in polynomial time.</p> <p>Furthermore, some experts <em>conjecture</em> that we cannot do much better, i.e. there are problems in <span class="math-container">$\mathsf{NP}$</span> that cannot be solved much more efficiently than brute-force search algorithms which take exponential amount of time. See the <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="noreferrer">Exponential Time Hypothesis</a> for more information. But this is not proven, it is only a <em>conjecture</em>. It just shows how far we are from finding polynomial time algorithms for arbitrary <span class="math-container">$\mathsf{NP}$</span> problems.</p> <p>This association with exponential time confuses some people: they think incorrectly that <span class="math-container">$\mathsf{NP}$</span> problems <em>require</em> exponential-time to solve (or even worse there are no algorithm for them at all). Stating that a problem is in <span class="math-container">$\mathsf{NP}$</span> does not mean a problem is <em>difficult</em> to solve, it just means that it is <em>easy</em> to verify, it is an <em>upper bound</em> on the difficulty of solving the problem, and many <span class="math-container">$\mathsf{NP}$</span> problems are easy to solve since <span class="math-container">$\mathsf{P}\subseteq\mathsf{NP}$</span>.</p> <p>Nevertheless, there are <span class="math-container">$\mathsf{NP}$</span> problems which <em>seem to</em> be hard to solve. I will return to this in when we discuss <span class="math-container">$\mathsf{NP}$</span>-hardness. </p> <hr> <h2>Lower Bounds <em>Seem</em> Difficult to Prove</h2> <p>OK, so we now know that there are <a href="http://en.wikipedia.org/wiki/List_of_NP-complete_problems" rel="noreferrer">many natural problems</a> that are in <span class="math-container">$\mathsf{NP}$</span> and we do not know any efficient way of solving them and we suspect that they really require exponential time to solve. Can we prove this? </p> <p>Unfortunately the task of proving <strong>lower bounds</strong> is very difficult. We <em>cannot</em> even prove that these problems require more than <em>linear time</em>! Let alone requiring exponential time.</p> <p>Proving linear-time lower bounds is rather easy: the algorithm needs to read the input after all. Proving super-linear lower bounds is a completely different story. We can prove super-linear lower bounds with more restrictions about the kind of algorithms we are considering, e.g. sorting algorithms using comparison, but we do not know lower-bounds without those restrictions.</p> <p>To prove an upper bound for a problem we just need to design a good enough algorithm. It often needs knowledge, creative thinking, and even ingenuity to come up with such an algorithm. </p> <p>However the task is considerably simpler compared to proving a lower bound. We have to show that <em>there are no good algorithms</em>. Not that we do not <em>know of</em> any good enough algorithms right now, but that <em>there does not exist any good algorithms</em>, that <em>no one will ever come up with a good algorithm</em>. Think about it for a minute if you have not before, how can we show such an <strong>impossibility result</strong>? </p> <p>This is another place where people get confused. Here "impossibility" is a <strong>mathematical impossibility</strong>, i.e. it is not a short coming on our part that some genius can fix in future. When we say impossible we mean it is absolutely impossible, as impossible as <span class="math-container">$1=0$</span>. No scientific advance can make it possible. That is what we are doing when we are proving lower bounds. </p> <p>To prove a lower bound, i.e. to show that a problem <em>requires</em> some amount of time to solve, means that we have to prove that <em>any</em> algorithm, even very ingenuous ones that do not know yet, cannot solve the problem faster. There are many intelligent ideas that we know of (greedy, matching, dynamic programming, linear programming, semidefinite programming, sum-of-squares programming, and many other intelligent ideas) and there are many many more that we do not know of yet. Ruling out one algorithm or one particular idea of designing algorithms is not sufficient, we need to rule out all of them, even those we do not know about yet, even those may not ever know about! And one can combine all of these in an algorithm, so we need to rule out their combinations also. There has been some progress towards showing that some ideas cannot solve difficult <span class="math-container">$\mathsf{NP}$</span> problems, e.g. greedy and its extensions cannot work, and there are some work related to dynamic programming algorithms, and there are some work on particular ways of using linear programming. But these are not even close to ruling out the intelligent ideas that we know of (search for lower-bounds in restricted models of computation if you are interested).</p> <hr> <h2>Barriers: Lower Bounds <em>Are</em> Difficult to Prove</h2> <p>On the other hand we have mathematical results called <a href="http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof" rel="noreferrer">barriers</a> that say that a lower-bound proof cannot be such and such, and such and such almost covers all techniques that we have used to prove lower bounds! In fact many researchers gave up working on proving lower bounds after Alexander Razbarov and Steven Rudich's <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="noreferrer">natural proofs</a> barrier result. It turns out that the existence of particular kind of lower-bound proofs would imply the insecurity of cryptographic pseudorandom number generators and many other cryptographic tools.</p> <p>I say almost because in recent years there has been some progress mainly by <a href="http://en.wikipedia.org/wiki/Ryan_Williams_%28computer_scientist%29" rel="noreferrer">Ryan Williams</a> that has been able to intelligently circumvent the barrier results, still the results so far are for very weak models of computation and quite far from ruling out general polynomial-time algorithms.</p> <p>But I am diverging. The main point I wanted to make was that proving lower bounds is difficult and we do not have strong lower bounds for general algorithms solving <span class="math-container">$\mathsf{NP}$</span> problems.</p> <p>[On the other hand, Ryan Williams' work shows that there are close connections between proving lower bounds and proving upper bounds. See <a href="https://www.youtube.com/watch?v=K2-Y4a3BtSE" rel="noreferrer">his talk at ICM 2014</a> if you are interested.]</p> <hr> <h2>Reductions: Solving a Problem Using Another Problem as a Subroutine/Oracle/Black Box</h2> <p>The idea of a reduction is very simple: to solve a problem, use an algorithm for another problem.</p> <p>Here is simple example: assume we want to compute the sum of a list of <span class="math-container">$n$</span> natural numbers and we have an algorithm <span class="math-container">$Sum$</span> that returns the sum of two given numbers. Can we use <span class="math-container">$Sum$</span> to add up the numbers in the list? Of course!</p> <p><strong>Problem:</strong></p> <blockquote> <p>Input: a list of <span class="math-container">$n$</span> natural numbers <span class="math-container">$x_1,\ldots,x_n$</span>,<br> Output: return <span class="math-container">$\sum_{i=1}^{n} x_i$</span>. </p> </blockquote> <p><strong>Reduction Algorithm:</strong></p> <blockquote> <ol> <li><span class="math-container">$s = 0$</span></li> <li>for <span class="math-container">$i$</span> from <span class="math-container">$1$</span> to <span class="math-container">$n$</span><br> 2.1. <span class="math-container">$s = Sum(s,x_i)$</span> </li> <li>return <span class="math-container">$s$</span> </li> </ol> </blockquote> <p>Here we are using <span class="math-container">$Sum$</span> in our algorithm as a <strong>subroutine</strong>. Note that we do not care about how <span class="math-container">$Sum$</span> works, it acts like <strong>black box</strong> for us, we do not care what is going on inside <span class="math-container">$Sum$</span>. We often refer to the subroutine <span class="math-container">$Sum$</span> as <strong>oracle</strong>. It is like <a href="https://en.wikipedia.org/wiki/Delphi#Oracle" rel="noreferrer">the oracle of Delphi</a> in Greek mythology, we ask questions and the oracle answers them and we use the answers.</p> <p>This is essentially what a reduction is: assume that we have algorithm for a problem and use it as an oracle to solve another problem. Here efficient means efficient assuming that the oracle answers in a unit of time, i.e. we count each execution of the oracle a single step.</p> <p>If the oracle returns a large answer we need to read it and that can take some time, so we should count the time it takes <em>us</em> to read the answer that oracle has given to us. Similarly for writing/asking the question from the oracle. But oracle works instantly, i.e. as soon as we ask the question from the oracle the oracle writes the answer for us in a single unit of time. All the work that oracle does is counted a single step, but this excludes the time it takes us to write the question and read the answer. </p> <p>Because we do not care how oracle works but only about the answers it returns we can make a simplification and consider the oracle to be the problem itself in place of an algorithm for it. In other words, we do not care if the oracle is not an algorithm, we do not care how oracles comes up with its replies.</p> <p>For example, <span class="math-container">$Sum$</span> in the question above is the addition function itself (not an algorithm for computing addition).</p> <p>We can ask multiple questions from an oracle, and the questions does not need to be predetermined: we can ask a question and based on the answer that oracle returns we perform some computations by ourselves and then ask another question based on the answer we got for the previous question.</p> <p>Another way of looking at this is thinking about it as an <strong>interactive computation</strong>. Interactive computation in itself is large topic so I will not get into it here, but I think mentioning this perspective of reductions can be helpful.</p> <p>An algorithm <span class="math-container">$A$</span> that uses a oracle/black box <span class="math-container">$O$</span> is usually denoted as <span class="math-container">$A^O$</span>.</p> <p>The reduction we discussed above is the most general form of a reduction and is known as <strong>black-box reduction</strong> (a.k.a. <strong>oracle reduction</strong>, <strong>Turing reduction</strong>).</p> <p>More formally:</p> <blockquote> <p>We say that problem <span class="math-container">$Q$</span> is black-box reducible to problem <span class="math-container">$O$</span> and write <span class="math-container">$Q \leq_T O$</span> iff<br> there is an algorithm <span class="math-container">$A$</span> such that for all inputs <span class="math-container">$x$</span>,<br> <span class="math-container">$Q(x) = A^O(x)$</span>.</p> </blockquote> <p>In other words if there is an algorithm <span class="math-container">$A$</span> which uses the oracle <span class="math-container">$O$</span> as a subroutine and solves problem <span class="math-container">$Q$</span>.</p> <p>If our reduction algorithm <span class="math-container">$A$</span> runs in polynomial time we call it a <strong>polynomial-time black-box reduction</strong> or simply a <strong>Cook reduction</strong> (in honor of <a href="http://www.cs.toronto.edu/~sacook/" rel="noreferrer">Stephen A. Cook</a>) and write <span class="math-container">$Q\leq^\mathsf{P}_T O$</span>. (The subscript <span class="math-container">$T$</span> stands for "Turing" in the honor of <a href="http://en.wikipedia.org/wiki/Alan_Turing" rel="noreferrer">Alan Turing</a>).</p> <p>However we may want to put some restrictions on the way the reduction algorithm interacts with the oracle. There are several restrictions that are studied but the most useful restriction is the one called <strong>many-one reductions</strong> (a.k.a. <strong>mapping reductions</strong>). </p> <p>The idea here is that on a given input <span class="math-container">$x$</span>, we perform some polynomial-time computation and generate a <span class="math-container">$y$</span> that is an instance of the problem the oracle solves. We then ask the oracle and return the answer it returns to us. We are allowed to ask a single question from the oracle and the oracle's answers is what will be returned.</p> <p>More formally,</p> <blockquote> <p>We say that problem <span class="math-container">$Q$</span> is many-one reducible to problem <span class="math-container">$O$</span> and write <span class="math-container">$Q \leq_m O$</span> iff<br> there is an algorithm <span class="math-container">$A$</span> such that for all inputs <span class="math-container">$x$</span>,<br> <span class="math-container">$Q(x) = O(A(x))$</span>.</p> </blockquote> <p>When the reduction algorithm is polynomial time we call it <strong>polynomial-time many-one reduction</strong> or simply <strong>Karp reduction</strong> (in honor of <a href="http://en.wikipedia.org/wiki/Richard_M._Karp" rel="noreferrer">Richard M. Karp</a>) and denote it by <span class="math-container">$Q \leq_m^\mathsf{P} O$</span>.</p> <p>The main reason for the interest in this particular non-interactive reduction is that it preserves <span class="math-container">$\mathsf{NP}$</span> problems: if there is a polynomial-time many-one reduction from a problem <span class="math-container">$A$</span> to an <span class="math-container">$\mathsf{NP}$</span> problem <span class="math-container">$B$</span>, then <span class="math-container">$A$</span> is also in <span class="math-container">$\mathsf{NP}$</span>.</p> <p>The simple notion of reduction is one of the most fundamental notions in complexity theory along with <span class="math-container">$\mathsf{P}$</span>, <span class="math-container">$\mathsf{NP}$</span>, and <span class="math-container">$\mathsf{NP}$</span>-complete (which we will discuss below).</p> <hr> <p><strong>The post has become too long and exceeds the limit of an answer (30000 characters). I will continue the answer in <a href="https://cs.stackexchange.com/a/18666/41">Part II</a>.</strong></p> https://cs.stackexchange.com/questions/9556/-/14740#14740 8 Answer by Michael for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? Michael https://cs.stackexchange.com/users/10447 2013-10-01T20:47:16Z 2013-10-01T20:47:16Z <p>Copying my answer to a similar question on Stack Overflow:</p> <p>The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems".</p> <p>When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have a choice: either solve it as you would a "word problem", or try to plug in each of the answers given to you, and pick the candidate answer that fits.</p> <p>It often happens that a "multiple choice problem" is much easier than the corresponding "word problem": substituting the candidate answers and checking whether they fit may require significantly less effort than finding the right answer from scratch.</p> <p>Now, if we would agree the effort that takes polynomial time "easy" then the class P would consist of "easy word problems", and the class NP would consist of "easy multiple choice problems".</p> <p>The essence of P v. NP is the question: "Are there any easy multiple choice problems that are not easy as word problems"? That is, are there problems for which it's easy to verify the validity of a given answer but finding that answer from scratch is difficult?</p> <p>Now that we understand intuitively what NP is, we have to challenge our intuition. It turns out that there are "multiple choice problems" that, in some sense, are hardest of them all: if one would find a solution to one of those "hardest of them all" problems one would be able to find a solution to ALL NP problems! When Cook discovered this 40 years ago it came as a complete surprise. These "hardest of them all" problems are known as NP-hard. If you find a "word problem solution" to one of them you would automatically find a "word problem solution" to each and every "easy multiple choice problem"!</p> <p>Finally, NP-complete problems are those that are simultaneously NP and NP-hard. Following our analogy, they are simultaneously "easy as multiple choice problems" and "the hardest of them all as word problems".</p> https://cs.stackexchange.com/questions/9556/-/18666#18666 176 Answer by Kaveh for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? Kaveh https://cs.stackexchange.com/users/41 2013-12-05T22:19:21Z 2017-07-12T10:59:41Z <h1>Part II</h1> <p>Continued from <a href="https://cs.stackexchange.com/a/9566/41">Part I</a>. </p> <p>The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two.</p> <h2>$\mathsf{NP}$-completeness: <em>Universal</em> $\mathsf{NP}$ Problems</h2> <p>OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{NP}$). As we discussed above, both of these are <em>upper-bounds</em>. Let's focus our attention for now on problems inside $\mathsf{NP}$ as amazingly many natural problems turn out to be inside $\mathsf{NP}$.</p> <p>Now sometimes we want to say that <em>a problem is difficult to solve</em>. But as we mentioned above we cannot use lower-bounds for this purpose: theoretically they are exactly what we would like to prove, however in practice we have not been very successful in proving lower bounds and in general they are hard to prove as we mentioned above. Is there still a way to say that <em>a problem is difficult to solve</em>?</p> <p>Here comes the notion of $\mathsf{NP}$-completeness. But before defining $\mathsf{NP}$-completeness let us have another look at reductions.</p> <h3>Reductions as <em>Relative Difficulty</em></h3> <p>We can think of <strong>lower-bounds as absolute difficulty</strong> of problems. Then we can think of <strong>reductions as relative difficulty</strong> of problems. We can take <em>a reductions from $A$ to $B$</em> as saying <em>$A$ is easier than $B$</em>. This is implicit in the $\leq$ notion we used for reductions. Formally, reductions give partial orders on problems. </p> <p>If we can efficiently reduce a problem $A$ to another problem $B$ then $A$ should not be more difficult than $B$ to solve. The intuition is as follows: </p> <p>Let $M^B$ be an efficient reduction from $A$ to $B$, i.e. $M$ is an efficient algorithm that uses $B$ and solves $A$. Let $N$ be an efficient algorithm that solves $B$. We can combine the efficient reduction $M^B$ and the efficient algorithm $N$ to obtain $M^N$ which is an efficient algorithm that solves $A$. </p> <p>This is because we can use an efficient subroutine in an efficient algorithm (where each subroutine call costs one unit of time) and the result is an efficient algorithm. This is a very nice closure property of polynomial-time algorithms and $\mathsf{P}$, it does not hold for many other complexity classes.</p> <h3>$\mathsf{NP}$-complete means most difficult $\mathsf{NP}$ problems</h3> <p>Now that we have a relative way of comparing difficulty of problems we can ask which problems are most difficult among problems in $\mathsf{NP}$? We call such problems <em>$\mathsf{NP}$-complete</em>.</p> <blockquote> <p><strong>$\mathsf{NP}$-complete problems are the most difficult $\mathsf{NP}$ problems</strong>,<br> if we can solve an $\mathsf{NP}$-complete problem efficiently, we can solve all $\mathsf{NP}$ problems efficiently.</p> </blockquote> <p>More formally, we say a decision problem $A$ is $\mathsf{NP}$-complete iff</p> <blockquote> <p>$A$ is in $\mathsf{NP}$, and<br> for all $\mathsf{NP}$ problems $B$, $B$ is polynomial-time many-one reducible to $A$ ($B\leq_m^\mathsf{P} A$).</p> </blockquote> <p>Another way to think about $\mathsf{NP}$-complete problems is to think about them as the complexity version of <a href="http://en.wikipedia.org/wiki/Universal_Turing_machine" rel="noreferrer">universal Turing machines</a>. An $\mathsf{NP}$-complete problem is <strong><a href="http://en.wikipedia.org/wiki/Universal_object" rel="noreferrer">universal</a></strong> among $\mathsf{NP}$ problems in a similar sense: you can use them to solve any $\mathsf{NP}$ problem.</p> <p>This is one of the reasons that good <a href="http://en.wikipedia.org/wiki/SAT_solver" rel="noreferrer">SAT-solvers</a> are important, particularly in the industry. SAT is $\mathsf{NP}$-complete (more on this later), so we can focus on designing very good algorithms (as much as we can) for solving SAT. To solve any other problem in $\mathsf{NP}$ we can convert the problem instance to a SAT instance and then use an industrial-quality highly-optimized SAT-solver.</p> <p>(Two other problems that lots of people work on optimizing their algorithms for them for practical usage in industry are <a href="http://en.wikipedia.org/wiki/Integer_programming" rel="noreferrer">Integer Programming</a> and <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel="noreferrer">Constraint Satisfaction Problem</a>. Depending on your problem and the instances you care about the optimized algorithms for one of these might perform better than the others.)</p> <p>If a problem satisfies the second condition in the definition of $\mathsf{NP}$-completeness (i.e. the universality condition)<br> we call the problem <em>$\mathsf{NP}$-hard</em>. </p> <p>$\mathsf{NP}$-hardness is a way of saying that a problem is difficult.</p> <p>I personally prefer to think about $\mathsf{NP}$-hardness as universality, so probably <em>$\mathsf{NP}$-universal</em> could have been a more correct name, since we do not know at the moment if they are really hard or it is just because we have not been able to find a polynomial-time algorithm for them). </p> <p>The name $\mathsf{NP}$-hard also confuses people to incorrectly think that $\mathsf{NP}$-hard problems are problems which are <em>absolutely</em> hard to solve. We do not know that yet, we only know that they are <em>as difficult as any $\mathsf{NP}$ problem</em> to solve. Though experts think it is unlikely it is still possible that all $\mathsf{NP}$ problems are easy and efficiently solvable. In other words, being as difficult as any other $\mathsf{NP}$ problem does not mean really difficult. That is only true if there is an $\mathsf{NP}$ problem which is <em>absolutely</em> hard (i.e. does not have any polynomial time algorithm).</p> <p>Now the questions are: </p> <ul> <li><p>Are there any $\mathsf{NP}$-complete problems?</p></li> <li><p>Do we know any of them?</p></li> </ul> <p>I have already given away the answer when we discussed SAT-solvers. The surprising thing is that many natural $\mathsf{NP}$ problems turn out to be $\mathsf{NP}$-complete (more on this later). So if we pick a randomly pick a natural problems in $\mathsf{NP}$, with very high probability it is either that we know a polynomial-time algorithm for it or that we know it is $\mathsf{NP}$-complete. The number of natural problems which are not known to be either is quite small (an important example is factoring integers, see <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">this list</a> for a list of similar problems).</p> <p>Before moving to examples of $\mathsf{NP}$-complete problems, note that we can give similar definitions for other complexity classes and define complexity classes like $\mathsf{ExpTime}$-complete. But as I said, $\mathsf{NP}$ has a very special place: unlike $\mathsf{NP}$ other complexity classes have few natural complete problems.</p> <p>(By a natural problem I mean a problem that people really care about solving, not problems that are defined artificially by people to demonstrate some point. We can modify any problem in a way that it remains essentially the same problem, e.g. we can change the answer for the input $p \lor \lnot p$ in SAT to be NO. We can define infinitely many distinct problems in a similar way without essentially changing the problem. But who would really care about these artificial problem by themselves?)</p> <h2>$\mathsf{NP}$-complete Problems: There are Universal Problems in $\mathsf{NP}$</h2> <p>First, note that if $A$ is $\mathsf{NP}$-hard and $A$ polynomial-time many-one reduces to $B$ then $B$ is also $\mathsf{NP}$-hard. We can solve any $\mathsf{NP}$ problem using $A$ and we can solve $A$ itself using $B$, so we can solve any $\mathsf{NP}$ problem using $B$!</p> <p>This is a very useful lemma. If we want to show that a problem is $\mathsf{NP}$-hard we have to show that we can reduce all $\mathsf{NP}$ problems to it, that is not easy because we know nothing about these problems other than that they are in $\mathsf{NP}$.</p> <p>Think about it for a second. It is quite amazing the first time we see this. We can prove all $\mathsf{NP}$ problems are reducible to SAT and without knowing anything about those problems other than the fact that they are in $\mathsf{NP}$!</p> <p>Fortunately we do not need to carry out this more than once. Once we show a problem like $SAT$ is $\mathsf{NP}$-hard for other problems we only need to reduce $SAT$ to them. For example, to show that $SubsetSum$ is $\mathsf{NP}$-hard we only need to give a reduction from $SAT$ to $SubsetSum$.</p> <p>OK, let's show there is an $\mathsf{NP}$-complete problem.</p> <h3>Universal Verifier is $\mathsf{NP}$-complete</h3> <p><strong>Note:</strong> <em>the following part might be a bit technical on the first reading.</em></p> <p>The first example is a bit artificial but I think it is simpler and useful for intuition. Recall the verifier definition of $\mathsf{NP}$. We want to define a problem that can be used to solve all of them. So why not just define the problem to be that?</p> <blockquote> <p><strong>Time-Bounded Universal Verifier</strong><br> Input: the code of an algorithm $V$ which gets an input and a proof, an input $x$, and two numbers $t$ and $k$.<br> Output: $YES$ if there is a proof of size at most $k$ s.t. it is accepted by $V$ for input $x$ in $t$-steps, $NO$ if there are no such proofs.</p> </blockquote> <p>It is not difficult to show this problem which I will call $UniVer$ is $\mathsf{NP}$-hard:</p> <blockquote> <p>Take a verifier $V$ for a problem in $\mathsf{NP}$. To check if there is proof for given input $x$, we pass the code of $V$ and $x$ to $UniVer$.<br> ($t$ and $k$ are upper-bounds on the running time of $V$ and the size of proofs we are looking for $x$. we need them to limit the running-time of $V$ and the size of proofs by polynomials in the size of $x$.)</p> </blockquote> <p>(Technical detail: the running time will be polynomial in $t$ and we would like to have the size of input be at least $t$ so we give $t$ in unary notation not binary. Similar $k$ is given in unary.)</p> <p>We still need to show that the problem itself is in $\mathsf{NP}$. To show the $UniVer$ is in $\mathsf{NP}$ we consider the following problem:</p> <blockquote> <p><strong>Time-Bounded Interpreter</strong><br> Input: the code of an algorithm $M$, an input $x$ for $M$, and a number $t$.<br> Output: $YES$ if the algorithm $M$ given input $x$ returns $YES$ in $t$ steps, $NO$ if it does not return $YES$ in $t$ steps.</p> </blockquote> <p>You can think of an algorithm roughly as the code of a $C$ program. It is not difficult to see this problem is in $\mathsf{P}$. It is essentially writing an interpreter, counting the number of steps, and stopping after $t$ steps.</p> <p>I will use the abbreviation $Interpreter$ for this problem.</p> <p>Now it is not difficult to see that $UniVer$ is in $\mathsf{NP}$: given input $M$, $x$, $t$, and $k$; and a suggested proof $c$; check if $c$ has size at most $k$ and then use $Interpreter$ to see if $M$ returns $YES$ on $x$ and $c$ in $t$ steps.</p> <h3>$SAT$ is $\mathsf{NP}$-complete</h3> <p>The universal verifier $UniVer$ is a bit artificial. It is not very useful to show other problems are $\mathsf{NP}$-hard. Giving a reducing from $UniVer$ is not much easier than giving a reduction from an arbitrary $\mathsf{NP}$ problem. We need problems which are simpler.</p> <p>Historically the first natural problem that was shown to be $\mathsf{NP}$-complete was <a href="http://en.wikipedia.org/wiki/Satisfiability" rel="noreferrer">$SAT$</a>.</p> <p>Recall that $SAT$ is the problem where we are given a propositional formula and we want to see if it is <em>satisfiable</em>, i.e. if we can assign true/false to the propositional variables to make it evaluate to true.</p> <blockquote> <p><strong>SAT</strong><br> Input: a propositional formula $\varphi$.<br> Output: $YES$ if $\varphi$ is satisfiable, $NO$ if it is not.</p> </blockquote> <p>It is not difficult to see that $SAT$ is in $\mathsf{NP}$. We can evaluate a given propositional formula on a given truth assignment in polynomial time. The verifier will get a truth assignment and will evaluate the formula on that truth assignment.</p> <hr> <p>To be written...</p> <p>SAT is $\mathsf{NP}$-hard</p> <h2>What does $\mathsf{NP}$-completeness mean for practice?</h2> <h2>What to do if you <em>have to</em> solve an $\mathsf{NP}$-complete problem?</h2> <h2>$\mathsf{P}$ vs. $\mathsf{NP}$</h2> <h2>What's Next? Where To Go From Here?</h2> https://cs.stackexchange.com/questions/9556/-/52498#52498 6 Answer by icc97 for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? icc97 https://cs.stackexchange.com/users/45605 2016-01-31T00:50:12Z 2016-01-31T17:01:26Z <p>For the basics, the <a href="https://www.youtube.com/watch?v=YX40hbAHx3s">P vs. NP and the Computational Complexity Zoo</a> video seems a whole lot simpler to understand.</p> <p>For a computer with a <strong>really big version of a problem</strong>:</p> <h3><strong>P problems</strong></h3> <p><em>easy</em> to solve (rubix cube)</p> <h3><strong>NP problems</strong></h3> <p><em>hard</em> - but checking answers is <em>easy</em> (sudoku) </p> <p>Perhaps these are all really P problems but we don't know it... <strong>P vs. NP</strong>.</p> <strong>NP-complete</strong> <p>Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).</p> <h3><strong>EXP problems</strong></h3> <p><em>really hard</em> (best next move in chess)</p> <h3><strong>NP-hard problems</strong></h3> <p><strong>Edit:</strong> NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's <a href="https://en.wikipedia.org/wiki/NP-hardness">NP-hard</a> Euler diagram is clearer on this.</p> <h2>Video summary</h2> <p><a href="https://i.stack.imgur.com/coRsj.png"><img src="https://i.stack.imgur.com/coRsj.png" alt="Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard"></a></p> <h2><a href="https://en.wikipedia.org/wiki/NP-hardness">Wikipedia NP-hard</a> Euler diagram</h2> <p><a href="https://i.stack.imgur.com/CFDuq.png"><img src="https://i.stack.imgur.com/CFDuq.png" alt="SVG Euler diagrams of P, NP, NP-complete, and NP-hard"></a></p> https://cs.stackexchange.com/questions/9556/-/112751#112751 0 Answer by Thomas C. G. de Vilhena for What is the definition of $P$, $NP$, $NP$-complete and $NP$-hard? Thomas C. G. de Vilhena https://cs.stackexchange.com/users/108515 2019-08-14T18:26:31Z 2019-08-14T18:26:31Z <p><strong>P</strong>, <strong>NP</strong>, <strong>NP-complete</strong> and <strong>NP-hard</strong> are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties:</p> <p><a href="https://i.stack.imgur.com/d7wRq.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/d7wRq.png" alt="complexity classes table"></a></p> <p><strong>Solvable in polynomial time:</strong> Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running time is upper bounded by a polynomial expression in the size of the input for the algorithm. Using Big-O notation this time complexity is defined as <code>O(n ^ k)</code>, where n is the size of the input and k a constant coefficient.</p> <p><strong>Solution verifiable in polynomial time:</strong> Defines decision problems for which a given solution can be verified by a DTM using a polynomial amount of computation time, even though obtaining the correct solution may require higher amounts of time.</p> <p><strong>Reduces any NP problem in polynomial time</strong>: Defines decision problems whose algorithms for solving them can be used to solve any NP problem after a polynomial time translation step.</p> <hr> <p>I've recently written an article about this subject providing more details, including a code demonstration for reducing an NP problem into an NP-hard problem: <a href="https://thomasvilhena.com/2019/08/complexity-classes-of-problems" rel="nofollow noreferrer">Complexity classes of problems</a></p>