EDA T12 — Notions of Intractability

Ilario Bonacina

ilario.bonacina+EDA@upc.edu

This presentation is an adaptation of material from Antoni Lozano and Conrado Martinez

Agenda

Last theory class

• Intractability
  • Time complexity
  • P vs NP

Today

• P vs NP
• Reductions
• NP-completeness

Before we start: Questions on previous material?

Recap

What is a decision problem?

What is the complexity class \mathsf{P}?

What is the complexity class \mathsf{EXPTIME}?

What is the complexity class \mathsf{NP}?

\mathsf{P} vs \mathsf{NP}

\mathsf{P}\subseteq \mathsf{NP}\subseteq \mathsf{EXPTIME}

\mathsf{P}\subseteq \mathsf{NP} (see last class )

\mathsf{NP}\subseteq \mathsf{EXPTIME}

Proof

Let A \in \mathsf{NP}. Hence, there is a polynomial p and a verifier V such that

• x \in A implies V(x,y ) = 1 for some witness y such that |y|≤p(|x|)
• x \notin A implies V(x,y) = 0 for all possible candidate witnesses y such that |y |≤p(|x|)

We can consider an exponential algorithm for A that looks for a witness:

input x
for all y such that |y|≤p(|x|)
  if V(x,y ) = 1 then
    return 1
return 0

The previous algorithm is exponential and decides A.

\mathsf{P}\neq \mathsf{EXPTIME}

So either \mathsf{P}\neq \mathsf{NP} or \mathsf{NP}\neq \mathsf{EXP} or both.

But, which is the case?

Deciding whether \mathsf{P}= \mathsf{NP} or \mathsf{P}\neq \mathsf{NP} is known as the \mathsf{P} vs \mathsf{NP} problem. It is one of the Millennium Problems of the Clay Mathematics Institute.

The \mathsf{P} vs \mathsf{NP} problem

With the current knowledge the following scenarios below are perfectly possible:

• \mathsf{P}\neq \mathsf{NP} and \mathsf{NP}\neq \mathsf{EXP},
• \mathsf{P}\neq \mathsf{NP} and \mathsf{NP}= \mathsf{EXP},
• \mathsf{P}= \mathsf{NP} and \mathsf{NP}\neq \mathsf{EXP},

It is also possible that \mathsf{P}=\mathsf{NP} and \mathsf{P}\neq \mathsf{NP} are both coherent with all the commonly accepted axioms of mathematics…

Impagliazzo’s 5 possible worlds

• Algorithmica
• Heuristica
• Pessiland
• Minicrypt
• Cryptomania

\mathsf{P} = \mathsf{NP} via some explicit algorithm or something morally equivalent like fast probabilistic algorithms for \mathsf{NP}.

\mathsf{NP} problems are hard in the worst case but easy on average.

\mathsf{NP} problems hard on average but no one-way functions exist. We can easily create hard \mathsf{NP} problems, but not hard \mathsf{NP} problems where we know the solution. This is the worst of all possible worlds, since not only can we not solve hard problems on average but we apparently do not get any cryptographic advantage from the hardness of these problems.

One-way functions exist but we do not have public-key cryptography.

Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.

Most computer scientist believe that \mathsf{P}\neq \mathsf{NP} is likely to be true, actually, most computer scientists would say we live in Cryptomania or Minicrypt.

Reductions

A first example

Imagine we want to decide whether a graph G is 3-colorable when the input is given as an adjacency matrix.

Someone gives us an algorithm (as a black-box) that solves the problem when the graph G is given as an adjacency list.

How can we solve our original problem?

Intuition

A decision problem A reduces to a decision problem B if we can use an algorithm for B as a “sub-routine” in an algorithm to solve A in a very simple way:

• transform the input x for A into an input x' for B
• apply the algorithm for B on x'
  • if x' is a YES-instance output YES
  • if x' is a NO-instance output NO

Is this correct?

To ensure correctness, we need the tranformation to preserve YES/NO instances, that is x is a YES-instance for problem A if and only if x' is a YES-instance for problem B.

Polynomial-time reduction \leq_p

Let A and B be two decision problems with input sets I and I'.

Definition 1 (Polynomial-time reduction) A reduces to B in polynomial time (A\leq_p B) if there exists a polynomial-time algorithm f: I\to I' such that for each x\in I

• there exists a polynomial p s.t. |f(x)|\leq |p(|x|)|
• x is a YES-instance for A if and only if f(x) is a YES-instance for B

Warning

In a polynomial-time reduction we are not allowed to exchange YES-instances of one problem with NO-instances of the other!

Basic-properties

• If A,B\in \mathsf{P} then A\leq_p B.
• If A\leq_p B and B\in \mathsf{P}, then A\in \mathsf{P}.
• For every decision problem A, A\leq_p A.
• For every decision problems A,B,C, if A\leq_p B and B\leq_p C, then A\leq_p C.

\mathsf{NP}\text{-}\mathsf{hard}

Definition 2 (\mathsf{NP}\text{-}\mathsf{hard}) A decision problem A is \mathsf{NP}\text{-}\mathsf{hard} if, for every B\in \mathsf{NP}, B\leq_p A.

If in addition A\in \mathsf{NP}, then A is \mathsf{NP}\text{-}\mathsf{complete}.

Theorem 1 Let A be a decision problem \mathsf{NP}\text{-}\mathsf{complete}. Then, \mathsf{P}=\mathsf{NP} if and only if A\in \mathsf{P}.

Theorem 2 (Ladner) If \mathsf{P}\neq \mathsf{NP} there is a decision problem A\in \mathsf{NP}\setminus \mathsf{P} which is not \mathsf{NP}\text{-}\mathsf{complete}.

Do \mathsf{NP}\text{-}\mathsf{complete} problems exist?

Yes! \mathtt{SAT} is \mathsf{NP}\text{-}\mathsf{complete}! (Cook-Levin’71)

Actually, a lot of interesting decision problems all over computer science are \mathsf{NP}\text{-}\mathsf{complete}! (starting from Karp’s list)

A propositional formula is a formula over Boolean variables using the logic connectives AND (\land), OR (\lor), and NOT (\lnot).¹

A propositional formula F over the Boolean variables x_1,\dots,x_n is satisfiable if there exists an assignment from x_1,\dots,x_n to \{0,1\} which evaluates the formula F to true (i.e. 1).

1. Quantifiers (\forall,\exists) are not allowed in propositional formulas.

\mathtt{SAT} and \mathtt{CNF\text{-}SAT}

\mathtt{SAT}: given as input propositional formula F, is it satisfiable?

\mathtt{CNF\text{-}SAT}: given as input a CNF formula F, is it satisfiable?
A propositional formula is in Conjunctive Normal Form (CNF) if it is an AND of clauses, where a clause is an OR or variables and negated variables (literals).

Theorem 3 (Cook-Levin (1971)) \mathtt{SAT} and \mathtt{CNF\text{-}SAT} are \mathsf{NP}\text{-}\mathsf{complete}.

Proof. (sketch)

• \mathtt{SAT} and \mathtt{CNF\text{-}SAT} are in \mathsf{NP}. Why?
• \mathtt{CNF\text{-}SAT} is \mathsf{NP}\text{-}\mathsf{hard}: we don’t see the full argument in this course. The idea is that if the input is encoded in binary, any non-deterministic algorithm A can be implemented with a propositional formula \varphi with size polynomial in the input.

How to show that a decision problem A is \mathsf{NP}\text{-}\mathsf{complete}?

• Show that A is in \mathsf{NP}.

This is usually simple. Figure out which are the witnesses, prove their size is polynomial in the size of the input, and devise a polynomial time verifier.

• Show that for some \mathsf{NP}\text{-}\mathsf{complete} problem B, B\leq_p A.

For the moment we know only two \mathsf{NP}\text{-}\mathsf{complete} problems: \mathtt{SAT} and \mathtt{CNF\text{-}SAT}. Now we will construct many more.

A web of reductions

A\to B means that we show A\geq_p B. We only draw the \to we use to prove their \mathsf{NP}-completeness.

• \mathtt{SAT}
• \mathtt{CNF\text{-}SAT}
• \mathtt{3\text{-}SAT}
• \mathtt{CLIQUE}
• \mathtt{INDIPENDENT\text{-}SET}
• \mathtt{VERTEX\text{-}COVER}
• \mathtt{k\text{-}COLORABILITY} (k\geq 3)
• \mathtt{HAMILTONIAN}-\mathtt{CYCLE} / \mathtt{PATH}
• \mathtt{SUBSET}-\mathtt{SUM}
• \mathtt{KNAPSACK}
• \mathtt{TSP}

\mathtt{SAT}: given as input propositional formula F, is it satisfiable?

\mathtt{CNF\text{-}SAT}: given as input a CNF formula F, is it satisfiable?
A propositional formula is in Conjunctive Normal Form (CNF) if it is an AND of clauses, where a clause is an OR or variables and negated variables (literals).

\mathtt{3\text{-}SAT}: given a CNF formula F with only 3 literals per clause, is F satisfiable?

\mathtt{CLIQUE}: given a graph G and k\in \mathbb N, does G contain a k-clique as a subgraph?

\mathtt{INDIPENDENT\text{-}SET}: given a graph G and k\in \mathbb N, does G contain k vertices not adjacent to each other?

\mathtt{VERTEX\text{-}COVER}: given a graph G and k\in \mathbb N, does G contain k vertices such that each edge is adjacent to some of them?

\mathtt{3\text{-}COLORABILITY}: given a graph G, is it 3-colorable?

\mathtt{k\text{-}COLORABILITY} (k\geq 3): given a graph G, is it k-colorable?

\mathtt{HAMILTONIAN}-\mathtt{CYCLE}: given as input a graph G, does it contain a Hamiltonian cycle?

\mathtt{HAMILTONIAN}-\mathtt{PATH}: given as input a graph G, does it contain a Hamiltonian path?

\mathtt{SUBSET}-\mathtt{SUM}: given a_1, \dots, a_n, k\in \mathbb N, is there a subset S\subseteq \{1,2,\dots,n\} such that \sum_{i\in S}a_i=k?

\mathtt{KNAPSACK}: given n items with sizes s_1, s_2, \dots, s_n, values v_1, v_2, \dots, v_n, capacity B and value V, is there a subset S \subseteq\{1, 2, \dots, n\} such that \sum_{i\in S} s_i \leq B and \sum_{i\in S} v_i \geq V?

\mathtt{TSP} (Traveling Salesman Problem): given n cities, and distances d(i, j) between each pair of cities and k\in \mathbb N, does there exist a cycle of length \leq k that visits each city?

Upcoming classes

Wednesday

Problem class P7 on exhaustive search (do the exercises before class).

Next Monday

Theory class T13 again on Intractability (more reductions) and preparation for the second partial exam

Questions?