1. Asymptotic Notation & Complexity Classes

Asymptotic Notation

Big Oh Notation (upper bound): a function $g:\mathbb{N}\to \mathbb{N}$ eventually dominates a function $f:\mathbb{N}\to \mathbb{N}$ if there is some constant $c>0$ such that:

$$\boxed{\exists N\in \mathbb{N}\left(\begin{array}{c}\forall n>N;f(n)\le c\cdot g(n)\end{array}\right)}$$

Alternatively:

$$f(n)=O(g(n))\leftrightarrow f(n)\text{ is eventually dominated by }g(n)$$

Big Omega Notation (lower bound):

$$f(n)\in \Omega (g(n))\leftrightarrow f(n)\text{ eventually dominates }g(n)$$

Big Theta Notation (tight bounds):

$$\Theta (g(n))=O(g(n))\cap \Omega (g(n))$$

Decision Problems

Every problem for which the possible answers are true or false can be interpreted as a language:

$$L_p=\left\{\begin{array}{c}w\in {\Sigma }^{\ast }:w\text{ is instance of problem }P\text{ whose answer is }\top \end{array}\right\}$$

Time Complexity

Given a (terminating) machine $M$, we can define a time function $t_M:{\Sigma }^{\ast }\to \mathbb{N}$:

$$t_M(w):=\{\begin{array}{l}\text{number of steps required to}\\ \text{terminate on input }w\in {\Sigma }^{\ast }\end{array}$$

We define worst-case time complexity as $T_M(n):\mathbb{N}\to \mathbb{N}$:

$$T_M(n):=\text{max }\left\{\begin{array}{c}t(w):\text{ all words }w\text{ of length }n\end{array}\right\}$$

Complexity Classes P and NP

Polynomial Time (P)

Polynomial time (P): a language $L$ is said to be solvable in polynomial time if there exists a deterministic Turing Machine $M$ s.t.:

• $M$ accepts $L$
• $T_M(n)\in O(n^k)$ is eventually dominated by a polynomial function

We can define $P=\{\text{all problems in polynomial time}\}$.

Link to original

Non-deterministic Polynomial Time (NP)

Non-deterministic Polynomial time (NP): a language $L$ is said to be solvable in non-deterministic polynomial time if there exists an NDTM s.t.:

• $M$ accepts $L$
• $T_M(n)\in O(n^k)$ is eventually dominated by a polynomial function

We can define $NP$ in the same way.

Link to original