Probably Approximately Correct

P is (informally) the class of all problems that have polynomial-time algorithms. For simplicity, we focus on decision problems (those having a yes-or-no answer). This is not a serious assumption as using theory of Digital Logic, we can compute each bit of the answer.

NP (Non deterministic Polynomial-Time) is (informally) the class of all problems for which a solution can be verified in polynomial time.

Why is it called “non deterministic polynomial-time”? It’s a somewhat archaic name, but we’re stuck with it now.

NP-hard is the class of problems that are “at least as hard as any NP problem.” Formally, L is NP-hard if given a solution for L, you could solve every NP problem in polynomial time.

NP-complete is the class of problems that are both NP-hard and in NP. Informally, NP-complete problems are the “hardest problems in NP” — NP problems that somehow capture the difficulty of all other NP problems.

The problem of P vs NP can be informally formulated as follows:

Is there a better way to solve the problem that doesn’t involve a brute-force search? Exactly this question was asked in one of the most remarkable documents in the history of theoretical computer science: a letter that Kurt Godel sent to John von Neumann in 1956. (The full text of this letter is here.) In this letter, Godel concludes that if there were some general way to
avoid brute-force search, mathematicians would be out of a job!

After 52 years, we still don’t know the answer to Godel’s question. But there’s something remarkable that we do know. Look again at all of these problems. A priori, one might think brute-force search is avoidable for problem X, not for problem Y, etc. But in the 1970’s, people realized that in a very precise sense, they’re all the same problem. A polynomial-time algorithm for any one of them would imply a polynomial-time algorithm for all the rest. And if you could prove that there was no polynomial-time algorithm for one of them, that would imply that there is no polynomial-time algorithm for all the rest!

After all, one might wonder why this problem is taking such a long time — The reason is pretty simple — Informally, all known proof techniques (so-far in mathematics) do not work. More baffling is the fact that there are formal proofs that the current techniques do not work!

For those interested in complexity theory, kindly go through Complexity Zoo.

The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:

• Approximation: Instead of searching for an optimal solution, search for an “almost” optimal one.
• Randomization: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. See Monte Carlo method and Las Vegas method.
• Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.
• Parameterization: Often there are fast algorithms if certain parameters of the input are fixed.
• Heuristic: An algorithm that works “reasonably well” in many cases, but for which there is no proof that it is both always fast and always produces a good result. Metaheuristic approaches are often used.

One example of a heuristic algorithm is a suboptimal O(n log n) greedy coloring algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.