Probably Approximately Correct

This is what the orientation camp at MIT seems to offer! There are several other exciting events like Prudential Skywalk and Icecream, Cambridge Pub Crawl, Hiking Trip to White Mountains. There is lot of partying in near future :-) The complete itinerary is given here.

I hope most of the you are aware that Nandan Nilekani is heading the Unique Identification Authority of India — which aims at giving an unique smart card to every Indian.  This is an fictitious read on Nandan’s intro to parliament (Hattip: Anuj Gupta).

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.

How can Quantum physics aid Computing ?

It is widely believed that quantum computers cannot solve NP-Complete problems in Polynomial (.) time.

Quantum mechanics usually allows only linear transformations. In lay man terms, only those transformations which can be described by a matrix. Surprisingly, an arbitrary amount of non-linearity (say, non-zero quantity) will empower quantum computers to not only NP-Complete problems but also outside much harder ones.

Before, we go ahead and discuss on what can be the limits of efficient computation in this world and what can Quantum computers do ! We need to understand the limits of physics.

Physics has survived a long time without a unified theory. The reason is that, as far as experiment is concerned , we have been able to divide the world into two realms. In the atomic realm, quantum physics reigns, we can usually ignore gravity. We can treat space and time much as Newton did — as an unchanging background. The other realm is that of gravitation and cosmology. In that world, we can often ignore quantum phenomena.

But this cannot be anything other than a temporary, provisional solution. To go beyond, it is the first great unsolved problem in theoretical physics:

Combine general theory of relativity and quantum theory into a single theory that can claim to be the complete theory of nature. This is called the problem of Quantum gravity.

Besides the argument based on unification, there are problems specific to each theory that call for unification with each other.

Each theory has a problem of infinities. In nature, we are yet to encounter anything measurable that has an infinite value. But in both quantum theory and general relativity, we encounter predictions of physically sensible quantities becoming infinite.

General relativity has a problem with infinities because inside a black hole the density of matter and hence the strength of gravitational field quickly becomes infinite. That appears to have been the case very early in the history of the universe — at least, if we trust general relativity to its infancy. At the point at which the density becomes infinite, the equations of general relativity break down. Some people interpret this as time stopping, but a more sober view is that theory is just inadequate. For a long time, wise people have speculated that it is inadequate because the effects of quantum physics have been neglected.

The quantum theory, in turn, has its own trouble with infinities. They appear whenever you attempt to use quantum mechanics to describe fields, like the electromagnetic field. The problem is that the electric and magnetic fields have values at every point in space. This means that are an infinite number of variables. An infinite number of variables can lead to equations that get out of hand and predict infinite numbers when you ask questions about the probability of an event.

These are cases where we cannot help but feel that an essential part of physics has been left out. The problem of Quantum gravity is one of the 5 most fundamental problems in Physics.

PS: There are four more fundamental problems that ail current physics. They will be discussed in the subsequent  posts.