#computing #computation #mathematic # [[Epistemic status]] #shower-thought # NP completeness #to-digest >A language A is NP-hard if all languages in NP are Turing **polynomial time** (equivalently in this case, many-to-one poly-nomial time) reducible to A. Consequently, if any NP-hard language is in P, then P= NP. If A is NP-hard and A € NP, then we say A is NP-complete. NP is the set of problems where it is easy to show (give a certificate) that the answer is "yes," and P is the set of "yes-no" problems where it is easy to find the answer. The technical sense of "easy" is "doable by a deterministic Turing machine in polynomial time." The "P versus NP» question can be understood as whether problems for which it is easy to certify the answer are the same problems for which it is easy to find the answer. The relevance is this: Normally, we do not ask questions unless we can recognize easily in a certain sense when we are handed the correct answer. We are not normally interested in questions where it would take a lifetime of work to check whether or not you got the answer you want. NP is about those questions that we are likely to want answers to. > ~ [[Ming Li]] # External links