Describe NotesDecember3 here:

First we review BigO Notation:

O(n) --> Number of steps to solve problem is proportional to n.

• ^---size of input

--> theta(n) is precise bound

We did not previously have a precise model for what "number of steps" is. Now we do.

A "Step" is [drumroll] A Step Of A Turing Machine!

Anything that you can do to speed it up on an individual processor will only be constant time.

However, the type of Turing Machine you use *will* have an impact on the number of steps.

Simulating 2 tapes on a 1 tape Turing Machine costs n^2, therefore, our model for counting steps will be in a single tape Turing Machine, to retain integrity.

Nondeterminism

(AKA clever guessing) allows to compute lots of things simultaneously.

exponential (2ⁿ,Pⁿ) blowup to track

all possible {universal guesses sequences --> not tractable

A hierarchy, from lowest (left) to highest (right).

p=polynomial time computable | Nondeterministic Polynomial Time = NP | Exptime=Exponential time, deterministic TM.

Satisfiability

(X1 ^{X2) v ( X3} X1) v (X2 ^X4 x3)

It is either possible to satisfy this equation, or not.

Looking for an algorithm to satisfy this: deterministic: enumerate possibilities and verify. (i.e. brute force) nondet: guess correctly, but we still have to verify our guess is correct. NP problems w/ short certificates. In this case, you may not be able to find a solution quickly, but you can verify a solution in polynomial time.

Disjunctive Normal Form (like above) is ALWAYS satisfiable in polynomial time.

(X1 v [X2 v x2 v X4) ^{(X3 v [X1 v X2)} (X4 v X3 v [X2) (where [ is an overline)

Here we use a graph theory example, with coloring of nodes such every edge is connected to a certain color. If we assert that we *cannot* color it like that, it is not verifiable in polynomial time. However, If we assert that we can, a particular solution is verifiable or not in polynomial time.

If we can find an algorithm that guesses and is polynomial checkable, then the problem cannot be more difficult than NP. (but might be easier.) For example, you can use an elephant gun to shoot flies, but it might not be the most intelligent solution.

• NP-easy --> in NP, might be easier

• NP-hard --> Not easier than NP

• Those that are in NP *exactly* are called NP-Complete.

Cook's Theorem: SAT (the satisfiability problem) is NP-complete.

Suppose I have a solution to a problem in NP. Write down the computation history for the Turing Machine that solves that problem.

• Must only be in one state at a time.
• First row must be a start state.
• Final row must be an accepting state.
• Every 6-quare window must be legitimate according to the rules of the Turing machine.
  • (i.e. 3 consecutive Top (read) and Bottom (write))

If these 4 rules are true, then your solution works.

Reduction from any problem in NP to propositional satisfiability. If I could solve SAT, then I could solve any problem in NP.

Also, SAT is an element of NP (because we can guess solution and verify.)

If an easy solution to SAT is found, then all problems in NP are easy to solve (in P). Converting one NP problem to another NP problem takes only P time.

DNF SAT is easy, but that isn't good enough to bring all of NP into the light of P. This is because DNF SAT requires exploiting some happy shortcuts that can not be expanded back into the general case. Converting an arbitrary boolean formula to Disjunctive Normal Form and using DNF SAT would be awesome, but then the conversion is NP hard.

CNF SAT is also NP-Complete, as asserted by Lynn.

3-CNF-SAT is NPC. 3-CNF is Conjunctive Normal form, where each conjunct must have exactly 3 arguments. (a or b or c or d) -> (a or b or y) and (c or d or not y) :: Converting CNF -> 3-CNF take P time.

I really can't figure out how to explain Vertex Cover -> 3-CNF satisfiability. Anyone care to take a stab at it?