An algorithm has polynomial running time if there is a constant $c \geq 1$ such that for every input of length $n$, the algorithm takes $O(n^c)$ time.

An algorithm has exponential running time if there is a constant $c \geq 1$ such that for every input of length $n$, the algorithm takes $O(2^{n^c})$ time.

Complexity Class P

A decision problem is a problem for which the answer is "yes" or "no". The complexity class $P =$ set of all decision problems that can be solved in polynomial time. For example a sorting problem is not in $P$, since it does not output "yes" or "no".

Examples of problems in $P$:

• is a given input graph connected
• is a given input graph bipartite
• is a given input sequence sorted
• does a given input graph contain an Euler tour? An Euler tour is a path that traverses each edge exactly once

Other Problems

Hamiltonian Cycle

• input: An undirected graph $G = (V, E)$ stored using adjacency lists
• question: Does $G$ contain a Hamiltonian cycle? A Hamiltonian cycle is a cycle that traverses each vertex exactly once.

Right now on this planet, nobody knows how to solve this problem in polynomial time. Not known if this problem is in $P$!

Travelling Salesman Problem

• input:
  • A complete directed graph $G = (V, E)$, where each edge $(u,v) \in E$ has a weigh $wt(u,v) > 0$
  • An integer K
• question: Does $G$ contain a Hamiltonian cycle of total weight at most $K$?

Again we don't know if this problem is in $P$!

Subset-Sum

• input: A set $S$ of integers together with an integer $t$
• question: Is there a subset $S'$ of $S$ such that the sum of the subset is equal to $t$?

Not known if this problem is in $P$!

Clique

• input: An undirected graph $G = (V,E)$ together with an integer $K$
• question: DOes $G$ contain a clique (complete subgraph) with $K$ vertices?

Not known if this problem is in $P$!

Proving

For each of the 4 previous problems

• Not know if it can be solved in polynomial time
• If the answer to the question is YES, then
  • there is a "short" proof for this
    • "short" means the length of the proof is "polynomial in the length of the input"
  • if someones gives us such a short proof, then we can "easily" verify this proof
    • here "easily" means "in polynomial time"

How to check if proof is correct?

Hamiltonian cycle

proof/solution: sequence $v_1, ..., v_k$ of vertices

verification:

• $k=n$?
• no duplicates in $v_1, ..., v_k$
• For each $1 \leq i < k-1, {v_i, v_{i+1}}$ is an edge?
• ${v_k, v_1} is an edge?

TSP

proof/solution: sequence $v_1, ..., v_k$ of vertices

verification:

• $k=n$?
• no duplicates in $v_1, ..., v_k$
• Do we have $\sum_{i=1}^{k-1} wt(v_i, v_{i+1}) + wt (v_k, v_1) \leq K$?

Subset-sum

proof/solution: A set $S'$

verification:

• is $S'$ a subset of S?
• Do we have sum of subset $=t$?

Clique

proof/solution: A set $V'$

verification:

• is $V'$ a subset of V?
• Do we have $|V'| = K$?
• For each $u,v \in V'$ such that $u \neq v$, is ${u,v}$ an edge in $E$?

Complexity Class NP

A decision problem $A$ is in $NP$ if

• for a given input $I$, the answer to the question $A(I)$ is YES, then there exists a proof/solution/certificate $C$ such that
  • $C$ is short (polynomial size in the length of $I$)
  • in polynomial time, we can verify that $C$ is a correct proof for the fact that $A(I)$ = YES

$NP$ stands for Nondeterministic Polynomial

Formal P vs. NP

Language of a Decision Problem

The language of a decision problem is the set of all inputs (encoded as finite strings) for which the answer is YES.

Examples:

• HAM-CYCLE = {$G$ | $G$ is a graph that contains a Hamiltonian cycle}
• TSP = {($G, K$) | $G$ is a complete directed graph $G = (V,E)$, where each edge $(u,v) \in E$ has a weight $wt(u,v) > 0$, $K$ is an integer and $G$ contains a Hamiltonian cycle with total weight at most $K$.}
• SUBSET-SUM = {$(S, t) | S$ is a set of integers, $t$ is an integer and $\exists S' \subseteq S$ such that $\sum_{x \in S'} x = t$}

Complexity Class P

The language $L$ (of a decision problem) is in $P$ if the following is true. There exists an algorithm $A$ and a constant $c \geq 1$ such that for any input $x$,

• if $x \in L \iff A(x)$ returns YES.
• the running time of $A(x)$ is $O(n^c)$, where $n$ is the length of $x$.

Complexity Class NP

The language $L$ (of a decision problem) is in $NP$ if the following is true. There exists an algorithm $V$ and a constant $c \geq 1$ such that for any input $x$,

• $x \in L \iff$ there exists a certificate $y$ such that
  • $|y| = O(|x|^c)$
  • $V(x,y)$ returns YES
  • and the running time of $V(x,y)$ is polynomial in the length of $x$.

Observe that $V$ is a verification algorithm. It has 2 input parameters.

Example: Hamiltonian Cycle

{$G : G$ is a graph that has a Hamiltonian cycle} is in NP

Verification algorithm V takes as input

• graph $G = (V,E)$, where $n = |v|$
• certificate $v_1, v_2, ..., v_k$

It does the following:

1. check is $k = n$
2. check if $v_1, v_2, ..., v_k$ are all different
3. check if ${v_1, v_2}, {v_2, v_3}, ..., {v_n, v_1}$ are edges in $G$
4. if steps 1-3 were successful, return YES, otherwise NO.

Theorem

$P \subseteq NP$

Proof: Let $L$ be an arbitrary language (of a decision problem) in $P$. By definition, there is an algorithm $A$ such that for any input $x$,

• $x \in L \iff A(x)$ returns YES.
• The running time of $A(x)$ is polynomial in the length of x.

We have to show that $L$ is in $NP$. That is, we have to show that $L$ satisfies the definition of $NP$.

Therefore, we need a verification algorithm $V$. We define it in the following way: $V$ takes as input.

• the input $x$ for $A$
• and a certificate $y$

$V(x,y)$ does the following: it runs $A(x)$ and that's it! (It ignores $y$).

We then have the following:

• $x \in L$
  • $\iff A(x)$ returns YES
  • $\iff V(x,$ empty string $y$) returns YES
  • $\iff$ there exists a certificate $y$ such that
    • $|y|$ is polynomial in the length of $x$,
    • $V(x,y)$ returns YES
    • and the running time of $V(x,y)$ is polynomial in the length of $x$.

Therefore $L$ is in NP.

Big Question

Is $P=NP$ or $P \neq NP$? Most people believe the latter.

If we want to prove that $P \neq NP$, then we have to show that there exists a language $L$ (of a decision problem) such that

• $L \in NP$
• $L \not\in P$.

Such an $L$ must be "difficult". So we should look at the "most difficult" problems.

But what does this mean? How can we measure how difficult a problem is?

Reductions

Polynomial-Time Reduction

Let $L$ and $L'$ be two languages. We say that $L$ is a polynomial-time reducible to $L'$ if the following is true: there exists a function $f$ which satisfies the following famous 3 properties:

• $f$ maps inputs for $L$ to inputs for $L'$
• for ever input $x$ for $L$, $x \in L \iff f(x) \in L'$
• for every input $x$ for $L$, $f(x)$ can be computed in time that is polynomial in the length of $x$.

Notation: $L \leq_P L'$

Theorem

If $L \leq_P L'$ and $L' \in P$, then $L \in P$.

Intuition:

• $L' \in P$ means "$L'$ is easy"
• $L \leq_P L'$ means "$L$ is easer than $L'$".
• So $L$ is easy, $L \in P$.

Consider the following algorithm $A$: on input $x$,

• Compute $f(x)$
• Run $A'(f(x))$

We have $x \in L$

• $\iff f(x) \in L'$ by definition of reduction
• $\iff A'(f(x))$ returns YES by definition of $A'$
• $\iff A(x)$ returns YES by definition of $A$

The running time of $A$ is polynomial in the length of $x$. So $L \in P$.

About 3SAT

Consider a Boolean formula $\phi$ with variables $x_1, x_2, ..., x_n$ of the form $\phi = C_1 \land C_2 \land ... \land C_m$, where each $C_i$ is of the form $C_i = l_1^i \lor l^i_2 \lor l^i_3$. Each $l^i_j$ is a variable or the negation of a variable. $C_i$ is called a clause and $l_j^i$ is called a literal.

$phi = (x_1 \lor \neg x_1 \lor \neg x_2) \land (x_2 \lor x_3 \lor x_4) \land (x_1 \lor x_3 \lor \neg x_4) \land (\neg x_1 \lor x_3 \lor \neg x_4)$

We say that $\phi$ is satisfiable if there exists a truth value for each $x_1, x_2, ..., x_n$ such that $\phi$ is true.

3SAT = ${\phi | \phi is of the form above and \phi is satisfiable}$

We want to show that 3SAT $\leq_P$ INDEP - SET

Let $\phi$ be an input for 3SAT, $\phi = C_1 \land C_2 \land ... \land C_m$, each clause $C_i$ is the disjunction $(V)$ of 3 literals.

$(G;K)$ is obtained as follows:

• $K=m$(number of clauses)
• $G$ has $3m$ vertices, one vertex for each literal.
  • For each clause, the literals in this clause form a triangle in $G$.
  • Additionally, there is an edge between any pair of opposite literals.

Theorem

The relation $\leq_P$ is transitive: $L \leq_P L'$ and $L' \leq_P L'' \Rightarrow L \leq_P L''$

NP-Hard and NP-Complete

The language $L$ is $NP$-Hard if

• for all $L' \in NP$, $L' \leq_P L$

The language $L$ of a decision problem is $NP$-Complete if

• $L \in NP$
• and for all $L' \in NP$, $L' \leq_P L$

It is not clear if a $NP$-Complete problem exists.

Intuitively, this means that $L$ belongs to the most difficult problems in $NP$. This what we were looking for in Formal P vs. NP.

Theorem

Assume that $L$ is $NP$-Complete. Then $L \in P \iff P = NP$.

Intuition:

• If $L \in P, L$ is easy
• $L$ is $NP$-Complete, so $L$ belongs to the most difficult problems in $NP$.
• If the most difficult problem in $NP$ turns out to be easy, then all problems in $NP$ are easy!

Theorem

$L$ is $NP$-Complete, $L \leq_P L'$, $L' \in NP \Rightarrow L'$ is $NP$-Complete.

Intuition:

• $L$ is $NP$-Complete, so $L$ belongs to the most difficult problems in $NP$.
• $L'$ is at least as difficult as $L$
• Then $L'$ also belongs to the most difficult problems in $NP$

Here is how to use this theorem; to show that $L'$ is $NP$-Complete,

• Show that $L' \in NP$
• Look for a problem $L$ that is "similar" to $L'$ and that is known to be $NP$-Complete
• Show that $L \leq_P L'$.

CIRCUIT-SAT

input: A Boolean circuit

• Directed acyclic graph, where vertices are gates
• AND-gates and OR-gates have indegree 2
• NOT-gates have indegree 1
• Known input gats have indegree 0 and are labeled TRUE or FALSE
• Unknown gates have indegree 0 and are labeled "?"
• There is one output gate (whose outdegree is 0)

question: is it possible to assign a truth-value to each unknown input gate, such that the output of the circuit is TRUE?

CIRCUIT-SAT = {$B$ | $B$ is a Boolean circuit for which there exist truth values for the unknown input gates such that the output of $B$ is TRUE}

To show that CIRCUIT-SAT is $NP$-Complete, we have to show two things:

1. CIRCUIT-SAT is in $NP$
   • Certificate: sequence of truth values for the unknown input gates
   • Verification: evaluate the circuit (in topological order)
2. Show that for all $L$ in $NP$, $L \leq_P$ CIRCUIT-SAT
   • Let $L \in NP$. We need a function $f$ such that
     1. $f$ takes any input $x$ for $L$ and produces an input $B = f(x)$ for CIRCUIT-SAT
     2. $x \in L \iff B \in$ CIRCUIT-SAT
     3. The time to compute $B$ is polynomial in the length of $x$

We know that $L \in NP$. So there is a verification algorithm $V$ such that

• the input to $V$ is $(x,y)$, where $x$ is an input for $L$ and $y$ is a certificate
• For every input $x$ to $L$,
  • $x \in L \iff$ there exists a certificate $y$ such that
    • $|y| \leq |x|^c$
    • $V(x,y)$ returns YES
    • and the running time of $V(x,y)$ is at most $|x|^c$

We now define the function $f$. Let $x$ be an input for $L$. Define a new algorithm $V_x$:

• input is a string $y$ of length at most $|x|^c$
• $V_x(y)$ runs $V(x,y)$
• If $V(x,y)$ terminates in at most most |x|^c' steps, then $V_x(y)$ terminates and returns the output of $V(x,y)$
• If $V(x,y)$ has not terminated after |x|^c' steps, then $V_x(y)$ terminates and returns NO.

Observe:

• Running time of algorithm $V_x$ is at most |x|^c'