RSS
people
Jul 20 2009

P, NP and Friends

By Prasant | Filled under: Complexity Theory

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.

3 Comments |
May 28 2009

All About Infinities

By Prasant | Filled under: Complexity Theory, Nerd interest

The set theory taught to us in the secondary school levels has a big trouble — It cannot be called a theory in the first place. For it suffers a contradiction, viz.,

Let us call a set “abnormal” if it is a member of itself, and “normal” otherwise. For example, take the set of all squares. That set is not itself a square, and therefore is not a member of the set of all squares. So it is “normal”. On the other hand, if we take the complementary set that contains all non-squares, that set is itself not a square and so should be one of its own members. It is “abnormal”.

Now we consider the set of all normal sets – let us give it a name: R. If R were abnormal, that is, if R were a member of itself, then since R only contains normal sets, R must be normal, which is contradictory to our original hypothesis: R is abnormal. So, R cannot be abnormal, which means R is normal. Further, since every normal set is a member of R, R itself must be a member of R, making R abnormal. Paradoxically, we are led to the contradiction that R is both normal and abnormal.

This paradox is, often, referred to as Russell’s Paradox. Fortunately, consistent set theories exist — One of them is Zermelo–Fraenkel set theory.

Coming back to the informal set theories taught to us — these are attributed to the legendary Georg Cantor. Besides set theory, he gave us the wonderful notion of countable sets, uncountable sets and infinities. In a revolutionary result, he claims the following–

Not all infinities are of the same size! He, also, claims - Give me an infinity and I shall construct an infinity bigger than yours!

Informally, he claims In particular, the power set of a countably infinite set is uncountably infinite.

There are few more interesting things that come out of Cantor’s Results –

  • The ratio number of problems that can be solved on a computer to those that cannot be solved is exactly equal to the ratio of number of Natural Numbers to Real Numbers.
  • He, also, goes on to prove that set of real numbers is the smallest infinity that one can find.
  • The number of Real numbers between 0 and 1 is exactly equal to the total number of Real numbers!
16 Comments | Tags: , ,
May 18 2009

A World Without Time

By Prasant | Filled under: Complexity Theory, Nerd interest

 In 1942, the logician Kurt  Gödel and Albert Einstein became close friends; they walked to and from their offices every day, exchanging ideas about science, philosophy, politics and the lost world of German science in which both had grown up. By 1949,  Gödel had produced a remarkable proof - “ In any universe described by the Theory of Relativity, time cannot exist.“ 

   Einestein endorsed this result reluctantly, but he could find no way to refute it, and in the half -century since then, neither has anyone else.  Among all the contributions of  Gödel - this one is certainly the Queen and most of the times goes unnoticed.

      In case, you are intersted to know more about this particular result of Gödel – refer “The Forgotten Legacy of  Gödel and Einstein” by Palle Yourgrau.

 ——-

        For those readers, who are unaware of  Gödel’s contributions to Computer Sciences and Mathematics; I compose this brief overview about Gödel’s result from Aaronsons’ lectures.

There’s an amazing result called Gödel’s Completeness Theorem, which says that these rules are all you ever need. In other words: if, starting from some set of axioms, you can’t derive a contradiction using these rules, then the axioms must have a model (i.e., they must be consistent). Conversely, if the axioms are inconsistent, then the inconsistency can be proven using these rules alone.

Well, alright, I guess a year later he proved the Incompleteness Theorem. See, the Completeness Theorem was his Master’s thesis, and the Incompleteness Theorem was his PhD thesis. Apparently, one of his PhD examiners didn’t want to give him a degree because the PhD thesis was “too similar to the Master’s thesis.”

The Incompleteness Theorem says that, given any consistent, computable set of axioms, there’s a true statement about the integers that can never be proved from those axioms. Here consistent means that you can’t derive a contradiction, while computable means that either there are finitely many axioms, or else if there are infinitely many, at least there’s an algorithm to generate all the axioms. (If we didn’t have the computability requirement, then we could simply take our “axioms” to consist of all true statements about the integers! In practice, that isn’t a very useful set of axioms.)

Once you have Turing’s results(there doesn’t exist a computer to solve the Halting problem), Gödel’s results fall out for free as a bonus. Why? Well, suppose the Incompleteness Theorem was false — that is, there existed a consistent, computable proof system F from which any statement about integers could be either proved or disproved. Then given a computer program, we could simply search through every possible proof in F, until we found either a proof that the program halts or a proof that it doesn’t halt. (This is possible because the statement that a particular computer program halts is ultimately just a statement about integers.) But this would give us an algorithm to solve the halting problem, which we already know is impossible. Therefore F can’t exist.

By thinking more carefully, we can actually squeeze out a stronger result —  if a system is consistent, then it can’t prove its own consistency!! 

Let P be a program that, given as input another program Q, tries to decide whether Q halts by the strategy above (i.e., searching through every possible proof and disproof that Q halts in some formal system F). Then , suppose we modify P to produce a new program P’ that

  1. runs forever if Q is proved to halt given its own code as input, or
  2. halts if Q is proved to run forever given its own code as input.

Now suppose we feed P’ its own code as input. Then we know that P’ will run forever, without ever discovering a proof or disproof that it halts. For P’ finds a proof that it halts, then it will run forever, and if it finds a proof that it runs forever, then it will halt, which is a contradiction.But there’s an obvious paradox: why isn’t the above argument, itself, a proof that P’ will run forever given its own code as input? And why won’t P’ discover this proof that it runs forever — and therefore halt, and therefore run forever, and therefore halt, etc.?

The answer is that, in “proving” that P’ runs forever, we made a hidden assumption: namely that the proof system F is consistent. If F was inconsistent, then there could perfectly well be a proof that P’ halts, even if the reality was that P’ ran forever.

But this means that, if F could prove that F was consistent, then F could also prove that P’ ran forever — thereby bringing back the above contradiction. The only possible conclusion is that if F is consistent, then F can’t prove its own consistency. This result is sometimes called Gödel’s Second Incompleteness Theorem.

3 Comments | Tags: ,