22. Time Complexity

Mar 24, 2022

Consider a deterministic TM $M$ that decides language $L$:

• for any string $w$ the computation of $M$ terminates in finite amount of transitions
• number of transitions == decision time

Now consider all strings of length $n$

• $T_M(n)$ = maximum time required to decide any string of length $n$

$TIME(T(N))$ => decidable by deterministic TM in time $O(T(n))$

• e.g. decidable in $O(n)$ time:

  • $\{a^{n}b:n\ge 0\}$
  • $\{a{b}^{n}aba:n,k\ge 0\}$
  • $\{b^n:n\text{ is even}\}$

• e.g. decidable in $O(n^2)$ time:

  • $\{a^n{b}^n:n\ge 0\}$
  • $\{w{w}^R:w\in \{a,b\}\}$
  • $\{ww:w\in \{a,b\}\}$

• e.g. decidable in $O(n^3)$ time:

  • CYK algorithm: $L_2$ = {$<G,w>$ : w is generated by CFG G }
  • matrix multiplication: $L_3$ = { $<M_a,M_2,M_3>$ : $n\times n$ matrices and $M_1\times M_2=M_3$ }

Polynomial time algorithms: TIME$(n^k)$ constant $k>0$

• represents tractable algorithms: for small $k$ we can decide the result fast

Classes: it can be shown TIME$(n^k)\subset$ TIME$(n^{k+1})$

Class P

${\displaystyle P=\bigcup _k\text{TIME}(n^k)}$

Polynomial time algorithms; "tractable" problems

e.g. $\{a^{n}b\}$, $\{ww\}$, CYK, matrix multiplication

Exponential

• $\text{TIME}(2^{n^k})$
• Represents intractable algorithms => solvable only for small instance
• solvable by brute force (expensive) => approximation algorithms approximate solution and usually tractable
• e.g. Hamiltonian path problem, clique problem, the satisfiability problem

Non-deterministic

Language class $\text{NTIME}(T(n))$

• a non-deterministic TM decides each string og length $n$ in time $O(T(n))$
• non-deterministic polynomial time algorithms $L\in \text{NTIME}(n^k)$

Class NP

${\displaystyle NP=\bigcup _k\text{NTIME}(n^k)}$

• e.g. satisfyability problem, non-deterministic algorithm:
  • guess an assignment of variables
  • check if this is a satisfying assignment
• the other exponential problems are in NP class

Alternative definition for NP: set of languages that have polynomial time verifier.

Verifier for language $L$ us an (deterministic) algorithm that checks if a certificate $c$ is a solution to the problem instance $w\in L$.

Theorem: Language $L$ is in NP if and only if it has polynomial time verifier

L is in NP => it has polynomial time verifier

Algorithm for polynomial time verifier: for each input pair $<w,c>$: run (polynomial time) NTM for L with input $w$ forcing the transition choices determined by $c$.

Observation: ${\displaystyle P\subseteq NP}$