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)




·         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