Theory of Computing

Video lectures  by Shai Simonson  are the best

Here is the first video from the series

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 proble 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 investiage 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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s