**Lecture 24 (Complexity Hierarchy), 12/4/17**

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

- To prove that a problem A is NP-complete: find a
reduction from B to A, where B is a known NP-complete problem
- The
*SUBSET-SUM*: example of problem that has nothing to do with graphs or formulas and looks easy *SUBSET-SUM*is in NP (the certificate is the subset which adds up to the sum value)- Polynomial-time reduction (PTR) from
*3-SAT*to*SUBSET-SUM* *Corollary*:*SUBSET-SUM*is NP-complete- Lots of NP-complete
problems:
*CLIQUE*,*HAMPATH*(before)*MAX*-*CUT*, 3-*COLOR*(from hwk),*SUBSET*-*SUM*(today), various scheduling or packing optimization problems… - Significance of NP-completeness
– if boss asks to implement an NP-complete decision problem (or the
corresponding general problem), can’t do it in PTIME!!!
- Note:
*COMPOSITES*is not NP-complete (a P-time algorithm for it was found in 2004)

- There is a connection between decision (Boolean)
problems that give YES/NO answers and corresponding real-world
“general” problems where FIND something (such as a k-clique,
or a Hamiltonian path, or the subset with the right sum).
- Clearly, if we can find something, we know it exists. What about the other direction?
- We can usually reduce a problem that finds a solution
(e.g.
*FIND-SUBSET-SUM or FIND-HAMPATH)*to the Boolean problem that tells us if the solution exists (PTIME reduction, calls subroutine*more than once)* - Example 1: Finding the
actual numbers (
*FIND-SUBSET-SUM*) by reducing to*SUBSET*-*SUM*(the trick of pruning unnecessary elements) - Example 2: finding satisfiable
assignment for 3SAT

·
**co-NP**
– class of problems whose complements are in **NP** (example: *PRIMES)*

**co-NP**is the class of problems for which there is a polynomial-time algorithm that can verify*NO*instances (sometimes called counterexamples) given the appropriate certificate.- Equivalently,
**co-NP**is the set of decision problems where the "no" instances can be accepted in polynomial time by a non-deterministic Turing machine. - P
is
**in**the intersection of NP and co-NP - Unless
P = NP, no
**NP**-complete problem can be in**co-NP** - We
don’t know if NP = co-NP (another open problem, besides P=NP)!
- It is possible that P≠NP,
yet NP=co-NP
- Note
*: COMPOSITES*was known to be in NP and co-NP, but turned out to be in P

·
EXPTIME
= U TIME(2^{nk})
(p. 298)

·
NP,
co-NP are subsets of EXPTIME

**·
**Final complexity picture (3 possible ways)

**Reading:**

- Finish chapter 7

**Skills:**

- Know new definitions,
understand new concept
- Know the definition of
SUBSET-SUM

- Understand PTR from
*3-SAT*to*SUBSET-SUM* - Understand the
connection between NP-complete decision problems and corresponding
real-world “general” problems
- Understand what is co-NP
and EXPTIME
- Understand why NP is a
subset of EXPTIME

**Notes:**

- A vector of n numbers between 0 and k-1 can be viewed
as an n-digit number in base k
- In a graph with
*n*nodes, the number of edges is at most quadratic (if there is at most one edge between any pair of nodes), but there can be an exponential number of paths. - Usually, reductions to show NP-completeness are tricky,
but not always; the PTIME reduction from
*CLIQUE*to*SUBGRAPH ISOMORPHISM*is simple, proving that*SUBGRAPH ISOMORPHISM*is NP-complete.