```November 19

* P

P is the class of all polynomially decidable languages

Theorem:  P is closed under complement.
If TM M decides L, then the complement of L is decided by the
version of M that inverts y and n (polynomial bound unaffected).

* We define complexity as a function of input length
(worst case amount of time used over all inputs of a given length).

The following code executes on the order of n instructions, and is thus said
to have time complexity O(n):

for i = 1 to n do
val = val*2;

The following code is O(n) because the constant (the increase of 2 in number
of operations) is ignored:

for i = 1 to n do
val1 = val1*2;
val2 = val2*2;
val3 = val3*2;

In contrast, the following code has time complexity O(n^2):

for i = 1 to n do
for j = 1 to n do
val = val*2;

For TM, the complexity of:
TIME = #transitions before halting
SPACE = #cells used during computation

* Show exponential growth charts

A "tractable" problem is a problem that is in P.

Although polynomial problems could be expensive (n^100), typically
polynomial time problems are low-order polynomial time

This distinction is useful because there are many problems which NOBODY
has found a polynomial algorithm to compute.

* Argument:  this only categorizes algorithms on worst-case performance
Better argument, though much more difficult, is average-case analysis
Phase transition

Average-case analysis difficult because we don't know distribution of input

P still useful as a first step, provides a good classification

All regular languages and all context-free languages are in P
(DFAs require only |w| time, and deciding if w in CFL takes only
polynomial time).

* Problems vs. languages

Many problems ask for an output value to be computed
(search the space of possible solutions for an optimal answer)

A decision problem is a yes/no version of a search problem such that the
ability to solve a search problem => the ability to solve a decision
problem (many times the converse is true as well).

Example

Search Problem:  Input = G, a CFG
Desired Output = shortest w such that w has to leftmost derivations
(if G is ambiguous) or "not ambiguous" if G is unambiguous

Decision Problem:  Input = G, a CFG
Desired Output = "yes" if G is ambiguous
"no" if G is unambiguous

In general we have taken a search problem and perhaps made it easier by
replacing it with a decision problem.  If the easier problem cannot be
solved in polynomially time, certainly the harder problem cannot be solved
in polynomial time.

* Some well-known problems

- Traveling Salesman Problem

Search Problem:  Given a complete graph with weights on the edges, find a
cycle of least total weight that visits each vertex exactly once.

Decision Problem:  TSP = {, k:  G is a complete graph with weights on
edges that contains a cycle of total weight <= k visiting each vertex
exactly once}

*
/|\
10 / | \ 5
/  |9 \
/ 6 |   \
*----|----*
\   |   /
\  |  /
9 \ | / 3
\|/
*

If the Decision Problem cannot be solved in polynomial time, the Search
Problem cannot be solved in polynomial time.

No known polynomial-time algorithm for TSP

- Reachability

Given a directed graph G <= VxV, where V = {v1, ..., vn} is a finite set,
and two nodes vi, vj in V, is there a path from vi to vj?

Is Reachability in P?

Decision Problem:  {:  G contains a path from vi to vj}

Reachability can be solved in in polynomial time.

Compute reflexive transitive closure of G in time O(n^3) by TM
This is shown in book
The reflexive transitive closure will shown if path from vi to vj.

Reachability is in P.

- Eulerian Cycles

Given a graph G, is there a closed path in G (first and last vertices are
the same) that uses each edge exactly once?

Given background on bridges

The path can visit each node many times of not at all if node disconnected.
A graph that contains such a path is a Eulerian graph.

G1 = ({v1,v2,v3,v4}, {(v1 v3), (v1 v4), (v2 v1), (v2 v3),
(v3 v1), (v3 v2), (v4 v2), (v4 v3)}

G2 = ({v1,v2,v3,v4,v5,v6,v7}, {(v1 v2), (v2 v3), (v3 v4), (v4 v5), (v5 v6),
(v6 v1), (v1 v7), (v7 v2), (v7 v3), (v7 v4),
(v7 v5), (v7 v6)}

G1 contains a Euler Cycle (v1, v3, v1, v4, v3, v4, v2, v3, v2, v1) and
G2 does not contain any Euler Cycles.

Decision Problem:  L = {:  G is Eulerian}

A graph is Eulerian iff
(a) For any u,v in V (neither is disconnected), there is a path from
u to v, and
(b) All nodes have equal numbers of incoming and outgoing edges.

Algorithm
1) Make sure all nodes are connected.
Compute reflexive transition closure in O(n^3) time,
then test n^2 connections
2) Test for equality of incoming and outgoing edges in O(n) time.

The Euler Cycle Problem is in P.

Notice that we showed the Euler Cycle Problem is in P by using the
established fact that Reachability is in P.
We "reduced" the Euler Cycle Problem to an already solved problem.

- Hamiltonian Cycle

Given a graph G = (V,E), find a cycle that contains each vertex in V.

Decision Problem:  HC = {: G is a Hamiltonian graph}.

How decide the language?
List all permutations of the vertices
Check to see if any permutation is a Hamiltonian cycle in the graph.

There are |V|! permutations of the matrices, thus the algorithm is
exponential.

- Boolean Satisfiability

Given a boolean formula consisting of
1) boolean variables x1, x2, ...
2) boolean connectives ^, v, -, -> <->
3) parentheses

Determine a "truth assignment" (a set of T/F values for the variables)
that causes the entire formula to have the value true.
A truth assignment that evaluation the formula to true is a
"satisfying assignment".
A formula that has at least one satisfying assignment is a
"satisfying fomula".

Decision Problem:  SAT = {f:  f is a satisfiable boolean formula}.

f = ((x1 -> x2) v -(--x1 <-> x3) v x4)) ^ -x2

has the satisfying assignment
f = 0->0 v -((-0<->1)v1)) ^ -0
= (1 v -(1v1)) ^ 1
= (1v0) ^ 1
= 1

The formula f thus belongs to SAT.

SAT does not have any known polynomial-time algorithms

P  = DTIME = Deterministic Polynomial Time
NP = NTIME = Nondeterministic Polynomial Time

+-----+     Open Question:  Does P = NP?
/   NP  \
|  +---+  |
| /  P  \ |
| \     / |
\ +---+ /
+-----+

NP is the class of languages that can be verified by a poynomial-time
algorithm.
```