Goal of Chapters 1-5: Analyze what problems can be solved,

*in theory*Goal of Chapter 7: Analyze what problems can be solved,

*in a reasonable amount of time*

DTM M halts on all inputs

Let f(n): N → N be the maximum number of steps M uses on w when |w| = n

We say M is an f(n) time TM, ie M runs in time f(n)

Many times we don't care about the exact function f

- Instead we only care about the largest power of n
- Use Big O notation to represent dominant term

Example: Time Complexity of TM M is O(n

^{2}) means- n
^{2}is the dominant term of the time complexity function of M

- n
Examples of Big O notation:

- n
^{3}+ n^{2}+ x is O(n^{2}) - 2n
^{6}+ 5n^{3}+ 4 is O(n^{6}) - Bubble sort is O(n
^{2})

- n
Why do we care about Big O

- When n is large, smaller terms are relatively unimportant
- Ignoring others simplifies analysis

Assume input size of

*n*Polynomial time complexity:

- Can be expressed as
*n*, for some^{k}*k*

- Can be expressed as
Exponential time complexity:

- Can be expressed as
*k*, for some^{n}*k*

- Can be expressed as

Theorem 7.8: Every

*t(n)*time multitape TM has an equivalent*O(t*time single-tape TM. (Assuming function^{2}(n))*t(n)*must be*t(n) ≥ n*.)This is a

*polynomial*increase in speed

Def. 7.9:

*N*is a NTM that is a decider. The*running time*of*N*is the function*f(n)*, the maximum number of steps than*N*uses in*any*branch of its computation of any input of length*n*.See Figure 7.10

- Deterministic: one branch accepts/rejects
- Nondeterministic: branches accept or reject

Th. 7.11: Every

*t(n)*NTM has an equivalent 2^{O(t(n))}time deterministic TM. In both cases, the machines are single tape, and*t(n)*≥*n*.This is an

*exponential*increase in speed

**P**is the class of languages that are*decidable*in polynomial time on a deterministic single-tape TM.P = ∪ TIME(

*n*), for all^{k}*k*P is the same for all models of computation that are polynomially equivalent to the deterministic TM.

P is roughly the same as the class problems that can be realistically solved on a computer.

Remember:

**Decidable**in polynomial time

*PATH*= {<*G, s, t>*| Directed graph*G*has a path from*s*to*t*}Theorem 7.14:

*PATH*∈ PProof of Theorem 7.14:

*M*= On input <*G, s, t*>, where*G*is a directed graph with nodes*s*and*t*:- Mark node
*s* - Repeat step 3 until no more nodes are marked
- Scan all edges of G. For edge (
*a, b*) where*a*is marked anb*b*is not marked, mark node*b*. - If
*t*is marked,*accept*. Otherwise,*reject*.

- Mark node
Use an adjacency matrix (ie table with a row and column for each node) to implement the matrix

We must decide a given input in polynomial time

For input of size

*n*:The number of stages must be polynomial number in

*n*The number of steps per stage must be polynomial number in

*n*Assumption: Encoding of input must be done in polynomial time wrt to the input size

We describe

*algorithms*, but they could be*Turing Machines*.

*RELPRIME*= {<*x, y>*|*s*and*t*are relatively prime}Theorem 7.15:

*RELPRIME*∈ PProof of Theorem 7.15:

*E*= On input <*x, y*>, where*x*and*y*are natural numbers in binary:- Repeat steps 2 and 3 until
*y*= 0: - Assign
*x*←*x*mod*y* - Swap
*x*and*y* - Output
*x*

- Repeat steps 2 and 3 until
*R*= On input <*x, y*>, where*x*and*y*are natural numbers in binary:- Run
*E*on <*x, y*> - If
*E*outputs 1,*accept*. Otherwise,*reject*.

- Run
Each stage of

*E*(except possible the first) at least halves the size of*x*

Theorem 7.16: Every CFL is decidable in polynomial time.

Is the CFL decidable language fast enough? No.

- This algorithm used a CNF grammar and tried all derivations less than the needed size

Sketch of proof of Theorem 7.16:

*E*= On input*w*=*w*_{1}...*w*:_{n}Assume grammar is in CNF

Build a table of all derivable substrings of w

- Build the table from short substrings to long ones
- If
*A → BC*is in G, and*B*and*C are in the table, add *A*to the table

If start symbol

*S*is in the table, the string is derivable*O(n*^{3}) algorithm

Building from partial solutions is called

**dynamic programming*Each stage of

*E*(except possible the first) at least halves the size of*x*