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^nb:n \geq 0\}\)
  • \(\{ab^naba: n,k \geq 0\}\)
  • \(\{b^n: n \text{ is even}\}\)

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

  • \(\{a^nb^n: n \geq 0\}\)
  • \(\{ww^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^nb\}\), \(\{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\)