**Lecture
23 (PTIME Reductions), 11/29/17**

** Concepts, definitions (in italics):**

·
Exam: 12/11/2017,
Monday 1-3pm, here

·
Approach
1 to P=NP: Polynomial-time verifiers

·
*Certificate* for w in L (a string) -
a string that "proves" that w belongs to L (“lucky guess”)

o
*Certificates for CLIQUE*? HAMPATH?* COMPOSITE?*

·
The
class *VP* is polynomially verifiable
problems/languages (p. 293)

·
*Verifier* is an algorithm similar to a
*decider*, inputs w and c

·
*Polynomial time verifier – *polynomial time in the length
of w

·
*Polynomially**
verifiable language – *has
a polynomial time verifier

·
*Theorem*: VP = NP (a language is decideable in non-deterministic polynomial time iff it is verifiable in polynomial time)

o So NP is a class of languages
that can be *verified* quickly, whereas
P is a class of languages that can be *decided*
quickly

o This is an alternate way to
capture the difference between P and NP, as opposed to *deterministic* vs. *non-deterministic
*deciders

·
One
more problem in NP: 3-*SAT *

o
Definitions
of *variables*, *literals, clauses,
formula, satisfiability*

o
The satisfying assignment serves as the certificate

·
*Polynomial-time
reductions*
(PTR) from A to B: A is polynomially reducible to B, written as A <=_{p}
B

·
*PTR
properties:*

1. if A <=_{p} B and B is in P, then A is
in P

2. if A <=_{p} B and A is not in P, then B
is not in P

3. if A <=_{p} B and B <=_{p} C, then A is <=_{p} C

·
Example:
PTR from *3-SAT *to* CLIQUE*
(p. 303)

·
*NP-complete
languages*:
languages in NP such all other languages in NP are polynomially
reducible to them

·
*Theorem
1* (importance
of NP-completeness): if there exists an NP-complete language which is in *P*,
then *P = NP*

·
3-*SAT*
was the first NP-complete language (proved in early 1970’s)

·
*Theorem
2 *(finding NP-complete problems): if A is NP-complete, B is in NP, and A <=_{p} B then B is NP-complete

·
Once 3-SAT is proven NP-complete, this theorem
allows us to use polynomial-time reductions to find other problems that are
NP-complete

·
*Corollary*: *CLIQUE* is
NP-complete

·
There are many many others (a whole book in
late 70’s)

**Reading:**

- chapter 7.3 finish
- chapter 7.4 (skip the proof of Theorem 7.37)

**Skills:**

- Know new definitions, understand new concepts
- Be able to outline the proof that VP = NP
- Know how to determine if a reduction is polynomial-time
- Understand the 3 PTR properties, be able to apply them
- Understand the PTIME reduction from 3-SAT to CLIQUE
- Understand the definition and the significance of
NP-completeness
- Understand the proof that CLIQUE is in
*NP* - Be able to prove the two theorems above about
NP-completeness.

**Notes:**

·
A
3-SAT formula is *satisfiable*
iff there exists an assignment (of truth values to
variables) so that every clause has at least one TRUE literal.

·
A
3-SAT formula is *not satisfiable*
iff for every assignment there is some clause whose
literals are all FALSE.

·
This book is full of NP-complete problems:

Garey, Michael R.; David S.
Johnson (1979). Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman