Difference between revisions of "Category:Theory of Computation"

Latest revision as of 13:36, 30 July 2015

Webpage for Theory of Computation

Video lectures by Shai Simonson are the best

Here is the first video from the series

{{#ev:youtube|HyUK5RAJg1c}}

Here are few terms which you must be familiar with

NP Complete

Recursively Enumerable Sets

This post describes about Computability concepts like SAT / NP completeness

P represents the class of problems that can be solved in polynomial time

NP represents the class of problems whose solutions can be verified in polynomial time

In other words, nondeterministically guess the solution and verify it in polynomial time. The guessing is nondeterministic and verification is polynomial. Thus nondeterministic polynomial (NP) time

If P were equal to NP, there would be amazing consequences. It means every problem verifiable in polynomial time could also be solved in polynomial time, all combinatorial optimizations could be solved in polynomial time. The curse of combinatorial explosions would be gone. Seems unlikely to be true… however NO counterproof (namely P!=NP) has been found.

SAT problem (introduced by scientist Cook)

The most important achievement of Cook is to show that P=NP iff a particular computational problem called SAT is in P.

Cook showed that any problem in NP can be transformed to a corresponding instance of SAT problem in such a way that the original has a solution iff the satisfiability instance has. Moreover, this translation can be done in polynomial time. In other words SAT problem is general enough to capture the structure of any problem in NP. It follows that if we can solve the SAT problem in polynomial time, then we would be able to construct a polynomial time algorithm to solve any problem in NP.

The SAT problem is one archetypal problem. In the field of combinatorial optimization , there is one archetypal problem (integer linear programming) and many combinatorial problems can be stated in terms of ILP.

NP Completeness (introduced by Prof. Karp)

Karp decided to investigate whether certain classic combinatorial problems long believed to be intractable were also archetypal in Cook’s sense. Karp called them “polynomial complete” (later known as NP complete)

A problem is said to be NP complete if it lies in the class NP and every problem in NP is polynomially reducible to it. Thus by Cook’s theorem the SAT problem is NP complete. To show a given problem in NP is NP complete it if sufficient to show that some problem already known to be NP complete is polynomial time reducible to it. By constructing a series of polynomial reductions, Karp showed that most problems were NP complete.