MIT 6.1220 — Lecture 13

Intractability (Part I)

§ Problem Types

We need to distinguish problems from instances.

The minimum cut problem asks for a minimal cut in any instance of a graph $G$ .
The shortest path problem asks for a shortest path on any instance of a graph $G$ .

The size of an instance is the number of bits needed to encode it.

The size of a graph is $|V| + |E|$ , roughly.
But actually, it's more like $|V| + 3|E|$ because each edge needs labels…
But actually, it's more complicated because it depends on the size of the edge weights, and so on…

We say an algorithm runs in time $O(t(n))$ if it can solve any instance of size $n$ in time $O(t(n))$ .

Remark. Instead of time, we could also consider space, or in-place-ness, or randomness as limited resources…

A problem is tractable if it has an algorithm with runtime $O(n^k)$ for some constant $k$ , and intractable otherwise.

From lecture, we know MST, min-cut, and shortest-path are all tractable.
But max-cut and longest-path are not known to be tractable.
- Max-cut can be approximated easily, though! But not longest-path…

There are many variants of problems.

Decision: Instances have YES / NO solutions.
Search: Instances have solutions of a certain quality or weight.
Optimization: Instances have solutions of a maximal quality or weight.

So the MST problem can have the following variants:

Decision: Does $G$ have a spanning tree of weight at most $K$ ?
Search: Find a spanning tree of $G$ of weight at most $K$ , if it exists.
Optimization: Find a minimum spanning tree of $G$ .

§ P, NP, coNP, EXP, and R

Only consider problems $\pi$ that are decision variants.

Definition (P). A problem $\pi$ is solvable in (deterministic) polynomial time iff there exists a (deterministic) algorithm $A_{\pi}$ and a constant $c$ such that for every instance $x$ , we have:

A_{\pi}(x) \text{ runs in time } O(|x|^c). ~~~ \textbf{ AND } ~~~ A_{\pi}(x) = \pi(x).

Definition (NP). A problem $\pi$ is solvable in non-deterministic polynomial time iff there exists a (deterministic) verifier algorithm $V_{\pi}$ and constants $c, c'$ such that for every instance $x$ of size $|x| = n$ , we have:

\begin{align*}& V_{\pi}(x, y) \text{ runs in time } O((|x| + |y|)^c). \\ \textbf{ AND } ~~~ & \pi(x) = \text{YES} \text{ iff there is a } y \text{ with } |y| \leq n^{c'} \text{ and } V_{\pi}(x, y) = \text{YES}.\end{align*}

All of min-cut, max-cut, min-path, and max-path are NP, with the desired $y$ being the cut / path itself.

Remark. Reminder that we're considering the decision variants of min-cut, max-cut, min-path, and max-path.

Definition (coNP). A problem $\pi$ is solvable in co-non-deterministic polynomial time iff there exists a (deterministic) verifier algorithm $V_{\pi}$ and constants $c, c'$ such that for every instance $x$ of size $|x| = n$ , we have:

\begin{align*}& V_{\pi}(x, y) \text{ runs in time } O((|x| + |y|)^c). \\ \textbf{ AND } ~~~ & \pi(x) = \text{NO} \text{ iff there is a } y \text{ with } |y| \leq n^{c'} \text{ and } V_{\pi}(x, y) = \text{YES}.\end{align*}

It's easy to find coNP problems by negating NP problems; “are all paths of weight $\leq k$ ?”, for example.

Claim. If $\pi \in \textbf{P}$ , then $\pi \in \textbf{NP}$ and $\pi \in \textbf{coNP}$ .

Proof: The desired NP and coNP algorithms just run the P algorithm (negated, for coNP). $\blacksquare$

These are the possible relationships between P, NP, and coNP.

Claim. It is not possible that $\textbf{P} = \textbf{NP} \neq \textbf{coNP}$ .

Proof: The intuition is that if a problem is in P, then NP and coNP are equally easy.

Formally, take any $\pi \in \textbf{coNP}$ . Then $\overline{\pi} \in \textbf{NP} = \textbf{P} \subseteq \textbf{coNP}$ , so $\overline{\pi} \in \textbf{coNP}$ . But then $\pi = \overline{\overline{\pi}} \in \textbf{NP} = \textbf{P}$ , done. $\blacksquare$

Definition (EXP). A problem $\pi$ is solvable in (deterministic) exponential time iff there exists a (deterministic) algorithm $A_{\pi}$ and a constant $c$ such that for every instance $x$ , we have:

A_{\pi}(x) \text{ runs in time } O(2^{|x|^c}). ~~~ \textbf{ AND } ~~~ A_{\pi}(x) = \pi(x).

Claim. All of P, NP, and coNP are in EXP.

Proof: Obviously $\textbf{P} \subseteq \textbf{EXP}$ because polynomial-time is faster than exponential-time.

For any $\pi \in \textbf{NP}$ (or $\textbf{coNP}$ ), we can solve $\pi$ by checking all $2^{\left(n^{c'}\right)}$ possible certificates. $\blacksquare$

Remark. We know that $\textbf{P} \neq \textbf{EXP}$ . This is the Deterministic Time Hierarchy Theorem.

The reason why we care about EXP is because it's a “higher level” of difficulty than NP and coNP.

Definition (R). A problem $\pi$ is solvable iff there exists a (deterministic) algorithm $A_{\pi}$ such that for every instance $x$ , we have:

A_{\pi}(x) \text{ runs in finite time.} ~~~ \textbf{ AND } ~~~ A_{\pi}(x) = \pi(x).

Remark. Primality testing is in P, which means it is solvable in $O((\log n)^c)$ time for some constant $c$ .

CYU: Why is $\log n$ here? This also implies primality testing is in NP; isn't that surprising?