Sipser: Section 7.4

From CSWiki

CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_7

1 NP-Completeness

NP-Completeness

Summary

NP-Complete problem is a problem in NP that its complexity relates to the entire NP class. Because the complexity of the entire NP are linked with a NP-Complete problem, one only needs to find polynomial solution for one NP-Complete problem in order to prove the equality between P and NP class, i.e. if NP-complete problem is a member of P then P = NP.

[edit]

Polynomial Time Reducibility

We define a new version of reducibility that considers the efficiency of computation.

Definition 7.28 (pg 276)

   A function f:  is a polynomial time computable function
   if some polynomial time TM M exists that halts with just f(w) on its tape, when started on any
   input w.

Definition 7.29 (pg 276)

   Language A is polynomial time mapping reducible ( or polynomial time reducible) to language B,
   written A  B, if a polynomial time computable function 
   f: * exists, where for every w, 
      .
   The function f is called the polynomial time reduction of A to B.

Theorem 7.31 (pg 277)

   If  and , then .

Theorem 7.32 (pg 278)

    $3 S A T$  is polynomial time reducible to  $C L I Q U E$ .

[edit]

Definition of NP-Completeness

    Definition 7.34 
       A language  $B$  is NP-Complete if it satisfies two conditions:
            1.  $B$  is NP
            2. every  $A$  in NP is polynomial time reducible to  $B$

The second part of the definition is a property known as NP-Hard. Formally,

A language  $A$  is NP-Hard if every language in NP is polynomial time reducible to  $A$ .

Proving NP-Completeness of a language:
If it is known that language $B$ is NP-Complete and $B \le_{p} C$ and $C \in NP$ , then language $C$ is NP-complete.

[edit]

The Cook-Levin theorem

    Cook-Levin theorem

describe the steps sipser uses

Proof of Cook-Levin Theorem

Show SAT is in NP
Show SAT in P => N= NP
Non-deterministic TM M with input w can be written as a boolean expression p
M accepts string w <=> p is satisfiable
<M, w> to p is in polynomial time.

[edit]

NP-Complete Problems

[edit]

SAT

A formula is boolean if each of the variables can be assigned the value T or F.
If there is some assignment of values that results in the formula evaluating to T, such formula is satisfiable.
SAT is NP-complete <=> Sat: a given boolean formula is satisfiable.

[edit]

3SAT

(summary of pg 278)

3SAT is a spcial case of the satisfiability problem whereby all formulas are in a special form.
3-cnf (cnf-formula) in conjunctive normal form.
A literal is a boolean variable or a negated boolean variable.
A clause is several literals in disjunct form.
A boolean formula is in cnf if it is the conjunction of clauses.
3cnf-formula has 3 literals.

CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_7

[edit]