```November 24

* 2-Satisfiability

SAT in which each clause is in conjunctive normal form
(a conjunction of disjunctions of literals) and has two or fewer literals

(x1vx2)^(x3v-x2)vx1v(-x1v-x2)^(x3vx4)^(-x3vx5)^(-x4v-x5)^(x4v-x3)

The 2-Satisfiability Problem is in P

Algorithm

1.  Purge
Look for single-literal clauses and set the variables to T
if positive (they must be true) and F is negative (they must be false)

x1 = T

Delete all clauses containing positive form of variable
Delete literal from clauses containing negative form of variable
If empty clause results then the formula is unsatisfiable

After O(n) steps ether the formula fails or the algorithm
halts with a set of two-literal clauses

(x3v-x2)^-x2^(x3vx4)^(-x3vx5)^(-x4v-x5)^(x4v-x3)

x2 = F

(x3vx4)^(-x3vx5)^(-x4v-x5)^(x4v-x3)

2.  Pick a remaining variable and try purge with a T value.  If fail,
try again with a F value.  Two purges for each of n variables and each
purge takes O(n) steps, so this requires a polynomial number of steps.

x3 = T

x5^(-x4v-x5)^x4

x5 = T
-x4^x4
This fails

x3 = F

x4^(-x4v-x5)

x4 = T
-x5
x5 = F
This succeeds

* NP

Many of the problems with an exponential run time can actually be solved
in polynomial time with a Nondeterministic Turing Machine.

NP is the class of all languages that are decided by a polynomially bounded
nondeterministic Turing Machine.

NP means "nondeterministically polynomial"

Remember that M decides a language if for each string in L, at least one
computation accepts the input.
Some or all other computations can reject input.

Only need one path that succeeds.

* SAT in NP

There exists a nondeterministic TM M that decides in polynomial time all
encodings of satisfiable Boolean formulae in conjunctive normal form.

Algorithm

1) Check to see if input w is a CNF Boolean formula (reject if not)
and count number of variables n
(polynomial time)

Second tape now contains the string \$I^n, (as many Is as the formula
has variables).

2) Nondeterministic phase
M writes a sequence of n T and F over the Is.
Different paths of M try all different sequences of values.

detal(q,I) = (q,T,R)
delta(q,I) = (q,F,R)
delta(q,B) = (q,B,S)

State q' continues the computation

3) Deterministic
M interprets string using second tape as a truth assignment
In pollynomial time accepts or rejects formula

This algorithm takes polynomial time because each separate path
only requires a polynomial number of steps (each path is just VERIFYING
a possible solution).  Encoding a deterministic algorithm to generate
and verify each path would require an exponential number of steps.

NP Problems are "polynomially veriable" problems.

* TSP in NP

A nondeterministic TM M nondeterministically generates all sequences.
M deterministically verifies if a sequence has total length <= k.

* EXP

A Turing Machine M is "exponentially bounded" if the machine always halts
after at most an exponential number of steps.

If L in NP, then L in EXP

* Certificates

NP algorithms

1) nondeterministically generate a string representing a possible solution
2) deterministically verify whether string is a solution

If the input is in the language, then at least one appropriate string exists.

A solution string is a "certificate" or a "witness".
All and only problems in NP have certificates.

A solution string must be of length that is polynomial in the length of the
input - otherwise, you may not be able to deterministically verify the
solution in polynomial time.

For SAT, verification is testing whether truth assignments satisfies formula.
For TSF, verification is testing whether total length is <= k.

* NP-Complete problems

NP-Complete problems are a special class of NP problems.
All NP problems can be reduced to any NP-complete problem in polynomial time.

If we assume that P is not equal to NP, then all NP-complete problems
are not in P.

If any one NP-complete problem can be solved in polynomial time, then
all problems in NP can be solved in polynomial time (P = NP).

Hamiltonian Cycle is an NP complete problem.
If we can decide HC in polynomial time, then we can solve every problem
in polynomial time.

If NP - P turns out to be nonempty, then HC in NP - P.

The NP complete languages are the "hardest" languages in NP.

* Why study NP Complete Problems?

Show cartoons

* How show that a problem is NP-Complete?

A language L is NP-complete if

1) L in NP, and
2) L' is polynomial-time reducible to L for every L' in NP

If a language L satisfies property 2 but not necessarily property 1, then
L is "NP-hard".

The set "NPC" is the set of NP-complete languages.

* Reducibility

A problem Q can be reduced to another problem Q' if any instance of Q can be
"easily rephrased" as an instance of Q'.  The solution of Q' thus provides a
solution to the instance of Q.

If L' can be reduced in polynomial time to L (a TM M can compute a function
from instances of L' to instances of L in polynomial time), the L is
"polynomial-time reducible" to L.

Algorithm for A
+------------------------------------+
|	                              |
|                                  +-|->"yes"
|                                 /  |
|   +-----+              +-------+   |
x --|-->| f   |---> f(x) --->| Alg B |   |
Instance of A |   +-----+Instance of B +-------+   |
|                                 \  |
|                                  +--->"no"
|	                              |
+------------------------------------+

This reduction shows that B is at least as hard as A.
If B is efficiently solvable, then so as A.
If A requires exponential time, then so does B.
```