NP and Time Complexity [cpsc/np-time-complexity]

Np (complexity class) is very important! Contains a large amount of natural problems

ex. Hamilton path, 3 color graph, graph isomorphism, satisfiable boolean formulas
Many problems in Np (complexity class) 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 $\text{TIME}\left( {t(n)} \right)$ .

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

NP and EXP [cpsc/np-exp]

Claim: Np (complexity class) $\subseteq$ Exp

Idea: For any $L \in NP$ , there is an NTM deciding $L$ in polynomial time. We can simulate it with a DTM that does the breadth-first search on the configuration tree. The tree has a number of nodes exponential in runtime of the NTM.

There are several open questions surrounding P (complexity class), Np (complexity class), and Exp:

Is $\text{P} \neq \text{N P}$ , i.e. $\text{P} \subset \text{NP}$ ?
Is $\text{NP} \neq \text{EXP}$ , i.e. $\text{NP} \subset \text{EXP}$ ?

The answer to either Q1 or Q2 is yes.

Proof: $\text{P} \subseteq \text{NP} \subseteq \text{EXP}$ , yet by the time hierarchy theorem $\text{P} \neq \text{EXP}$ . So either $\text{P} \neq \text{NP}$ or $\text{NP} \neq \text{EXP}$ (or both).