NP and Time Complexity [cpsc/NP-complexity]

NP is very important! Contains a large about of natural problems.

ex. Hamilton path, 3COLORGRAPH, graph isomorphism, satisfiable boolean formulas

Many problems in NP have “identical complexity”, i.e., are complete. (We’ll talk about this later.)

Definition 1. Runtime [runtime]

Complexity theory.
1. The runtime of a Turing machine $M$ is $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ : $f(n) = \max\left( {x \in \Sigma \ast ,|x| = n} \right)$ . (the number of steps of $M$ on input $n$ until it halts) (assume $M$ is a decider for simplicity)
2. The runtime of a nondeterministic Turing machine $\text{NTM}$ on input $X$ is max-length of any root-leaf path. For deciders – no infinite paths!

Recall:

Definition 2. TIME(t(n)) [TIME-tn]

$\text{TIME}\left( {t(n)} \right)$ is the class of all languages $L$ such that there exists a Turing machine with runtime $O\left( {t(n)} \right)$ that decides $L$ .

In briefer notation: $\text{TIME}\left( {t(n)} \right) = \left\{ {\text{language}\ L:\exists\ \text{TM}\ M\ \text{that decides}\ L\ \text{in time}\ O\left( {t(n)} \right)} \right\}$

Definition 1. P (complexity class) [P]

$P = \bigcup_{c > 0}\text{TIME}\left( n^{c} \right)$

Why is P a good definition for efficient computation?

Insensitive to model of computation: by the extended Church-Turing thesis, switching computational models “only” involves a polynomial slowdown
Closed under composition: can use polynomial time algorithm as a subroutine
In practice: algorithms usually can be improved. If we find an $O\left( n^{30} \right)$ time algorithm, it typically can be improved to, say, $O\left( n^{5} \right)$ time.

Example. 2COLORMAP

Let $G$ be a “map” of countries in the plane, where a coloring is valid if neighboring countries have different colors.

Question. The two color map does not work for every map. So consider it as a problem: $\text{2COLORMAP} = \left\{ {\left\langle G \right\rangle:G\ \text{has valid red/blue coloring}} \right\}$ . Is 2COLORMAP $\in$ P?

Answer. Yes! Start with an arbitrary country, set it to red, set their neighbors to blue, and continue. If there is a conflict, reject, if there is no conflict, accept.

It’s unknown if the three color map is in P. It’s known to be in EXP: $O\left( {3^{n}n^{2}} \right) \in O\left( 4^{n} \right)$

Definition 3. NTIME(t(n)) [NTIME-tn]

NTIME(𝑡(𝑛))={language𝐿:∃NTM𝑀thatdecides𝐿in time𝑂(𝑡(𝑛))}

NP (complexity class) [cpsc/NP]

$\text{NP} = \bigcup_{c > 0}\text{NTIME}\left( n^{c} \right)$

Obvious: P $\subset$ NP

Example. 3colormap $\in$ NP

Let’s prove that 3colormap is in NP.

Proof: Design a nondeterministic Turing machine to decide 3colormap in polynomial time.

Iterate through vertices
Nondetermistically pick a color for each vertex (a “lucky guess”)
Check all pairs of neighbors to see if they are the same color
If so reject, otherwise accept