EDA T11 — 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

• Exhaustive Search and Generation
  • Pruning
  • Branch & Bound
  • Several examples

Today

• Intractability
  • Time complexity
  • P vs NP

Before we start: Questions on previous material?

Complexity theory and Analysis of Algorithms

Analysis of Algorithms studies the amount of resources that an algorithm needs to solve a problem.

• “The cost of Mergesort to sort n items is \mathcal O(n\log n)”

Complexity Theory classifies problems according to the resources needed to solve them (with the best of the available algorithms)

• “The cost of any sorting algorithm¹ to sort n items in the worst-case is \Omega(n \log n)”

• “Deciding whether a graph is k-colorable has the same difficulty (modulo a polynomial factor) of deciding whether it has a Hamiltonian cycle.”

1. Any sorting algorithm which is only allowed to compare elements.

Decision problems

Definition 1 (Decision Problem) A decision problem is a computational problem with output YES/NO (or 0/1).

Equivalently, a decision problem is one where one has to determine whether the input satisfies (or not) a certain property.

• Given I the input set of a decision problem A, the set of positive instances is the set of all inputs that are YES instances, i.e. satisfy the property A.

• A set of decision problems give rise to a computational class.

We will only consider classes of problems that can be solved with a certain amount of resources.

Example 1 The following are decision problems:

• Given a graph G, is G Hamiltonian?
• Given a graph G, is G 3-colorable?
• Given a graph G and an integer k, is G k-colorable?
• Given a graph G and an integer k, does G contain a k-clique?
• Given a number n, is n prime?
  

What could be an example of a computational problem which is not a decision problem?

On the input

The instances of the problem will belong to some set I of inputs:

• natural numbers
• strings of symbols
• tuples of numbers
• graphs
• trees
• sequences of finite sets of numbers
• weighted DAGs
• …

Definition 2 (Size of the input) Given x\in I, the size of x, denoted |x| is the number of symbols (e.g., bits) of a standard (binary) encoding of x.

Decidability

Let f: \mathbb N \to \mathbb N be a function

Definition 3 A decision problem B with input set I is decidable in time f if there exists an algorithm A:I\to\{0,1\} such that

• the worst-case cost of A is \mathcal O(f), and
• for all x\in I,

A(x)=1 if and only if x is a positive instance of B.

Polynomial time \mathsf{P}

The complexity class \mathsf{P} is polynomial time: a decision problem A is in \mathsf{P} if there exists a constant k such that A is decidable in time n^k. More formally,

\mathsf{P}=\bigcup_{k\in \mathbb N}\mathsf{TIME}(n^k)\ , where \mathsf{TIME}(f):= \text{all the decision problems decidable in time $f$}

Some examples of decision problems in \mathsf{P}

• Given a DAG G and two vertices s and t in G, is t reachable from s?
• Given a number n, is n prime?¹
• Given a graph G and an integer k, is there a matching of size k in G?
• Given a graph G, is G connected?
• Given a graph G, is G 2-colorable?

1. This was proved by Agrawal, Kayal, and Saxena in 2004.

Exponential time \mathsf{EXPTIME}

The complexity class \mathsf{EXPTIME} is exponential time: a decision problem A is in \mathsf{EXPTIME} if there exists a constant k such that A is decidable in time 2^{n^k}. More formally,

\mathsf{EXPTIME}=\bigcup_{k\in \mathbb N}\mathsf{TIME}(2^{n^k})

Some examples of decision problems in \mathsf{EXPTIME}

• 3\text{-}\mathsf{COLORABILITY}: Given a graph G, is it 3-colorable?
  Open Problem: Is this problem in \mathsf{P}?
• \mathsf{FACTORING}: Given integers n and k, is there a number j with 1 < j < k and j dividing n?
  Open Problem: Is this problem in \mathsf{P}?
• \mathsf{Travelling Salesman Problem} (TSP): Given an input matrix of distances between n cities and an integer k, is there a route visiting all cities with total distance less than k?
  Open Problem: Is this problem in \mathsf{P}?
• …

Double exponential time \mathsf{2\text{-}EXPTIME}

The complexity class \mathsf{2\text{-}EXPTIME} is double-exponential time: a decision problem A is in \mathsf{2\text{-}EXPTIME} if there exists a constant k such that A is decidable in time 2^{2^{n^k}}. More formally,

\mathsf{2\text{-}EXPTIME}=\bigcup_{k\in \mathbb N}\mathsf{TIME}(2^{2^{n^k}})

Some examples of decision problems in \mathsf{2\text{-}EXPTIME}

• Given polynomials p_1,\dots,p_m and q, is q(x)=0 on all xs such that p_1(x)=\cdots=p_m(x)=0?
  Open Problem: Is this problem in \mathsf{EXPTIME}?
• A lot of problems from algebraic geometry…

Inclusions

\mathsf{P}\subsetneq \mathsf{EXPTIME}\subsetneq \mathsf{2\text{-}EXPTIME}

Seeing that \mathsf{P}\subseteq \mathsf{EXPTIME}\subseteq \mathsf{2\text{-}EXPTIME} is easy, what is difficult is to show that

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

and that

\mathsf{EXPTIME}\neq \mathsf{2\text{-}EXPTIME}

This is done by diagonalization (beyond the scope of this course).¹

1. This technique is inspired by Cantor’s proof that the cardinality of \mathbb R is strictly larger than the cardinality of \mathbb N.

Determinism

In deterministic algorithms the computation path from the input to the output is unique. All algorithms seen so far are deterministic.

The execution of a deterministic algorithm A on a given input x starts at some state and is described by a finite path in the “graph of states” leading to some state where the output is either 0 or 1 and the computation ends.

That path is uniquely determined by x.

Non-determinism

In a non-deterministic algorithm many distinct computational paths, forming a tree, are considered at once:

• if there is one computation path that “proves” that x\in A then that is the result;
• the algorithm will say x\notin A only when no proof that x\in A is to be found in any of the computational paths.

Non-deterministic algorithms are just like ordinary algorithms, but, given input x, they also can use the operation CHOOSE(y) which returns a value between 0 and y, as long as y\leq x.

On each invocation to CHOOSE the current computation path “forks” into y+ 1 branches, each one corresponding to one possible value returned by CHOOSE.

Example: \mathsf{FACTORING}

Given a number n, is n composite? That is, is there a number j with 1 < j < n such that j divides n?

input n

for j=2 to n-1
  if j divides n
    return 1
return 0    

exponential in the bitsize of the input

input n

j = CHOOSE(n-1)
  if j>1 and j divides n
    return 1
return 0    

polynomial in the bitsize of the input but non-deterministic

Open question: Is \mathsf{FACTORING}\in \mathsf{P}?

Example: k\mathsf{\text{-}COLORABILITY}

Given a graph G and an integer k, is G k-colorable?

input G=(V,E), k

for v=1 to |V|
  c[v]=CHOOSE(k)

for every edge {u,v} in E
  if c[u]==c[v]
    return 0
return 1

Non-deterministic polynomial time \mathsf{NP}

A decisional problem A with input set I is decidable in nondeterministic polynomial time iff there exist

• a set O
• a (deterministic) polynomial time algorithm V : I×O \to \{0,1\} (verifier) and
• a polynomial p such that,

for all x\in I, x is a positive case of A if and only if there exists a witness/certificate y\in O such that |y|\leq p(|x|) and V(x,y) = 1.

Definition 4 The set of all decision problems that can be decided in non-deterministic polynomial time is \mathsf{NP}.

Inclusions

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

But we know \mathsf{P}\neq \mathsf{EXPTIME}, so for sure either \mathsf{P}\neq\mathsf{NP} or \mathsf{NP}\neq \mathsf{EXPTIME} (or both).

So what is the case? Is \mathsf{P}=\mathsf{NP} or \mathsf{P}\neq \mathsf{NP}?¹

This is known as the \mathsf{P} vs \mathsf{NP} open problem and it is believed to be a very difficult mathematical open problem.²

1. There is also a third option, that both could be coherent with the usually assumed axioms of mathematics.

2. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a 1.000.000 USD$ prize for the first correct solution.

Upcoming classes

Wednesday

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

Next Monday

Theory class T12 again on Intractability: more on \mathsf{NP} (\mathsf{NP}-completeness and reductions)

Questions?