21.1. Decision vs Optimization

Both P and NP are classes of decision problems. A decision problem is a problem with a yes/no answer:

• Is this graph connected?
• Is this input sequence sorted?
• Does this graph have a vertex cover of size at most \(20\)?

An instance of a problem \(\boldsymbol{\Pi}\) is simply a particular input on which we want to solve \(\Pi\).

An instance \(I\) of a decision problem \(\Pi\) is a yes-instance if the answer to the question asked by \(\Pi\) on input \(I\) is yes. Otherwise, \(I\) is a no-instance.

While we are normally interested in problems that have more complex answers than simply yes or no, the importance of decision problems as a central tool for studying the difficulty of computational problems stems from two observations.

First, we can translate any optimization problem \(\Pi_o\) into a corresponding decision problem \(\Pi_d\), and it is easy to see that \(\Pi_o\) is no easier than \(\Pi_d\). Thus, if we can provide evidence that \(\Pi_d\) is hard to solve, then the same must be true for \(\Pi_o\).

Specifically, any optimization problem \(\Pi_o\) defines what a valid solution \(S\) for any given input instance \(I\) is, and it assigns an objective function value \(f(S)\) to each such solution \(S\). Given any instance \(I\) of \(\Pi_o\), the goal is to find a solution \(S\) that minimizes or maximizes \(f(S)\). If \(\Pi_o\) is a minimization problem, we can turn it into a decision problem \(\Pi_d\) by pairing every instance \(I\) with a real number \(k\). The question we want to answer then is whether \(I\) has a solution \(S\) with \(f(S) \le k\). For a maximization problem, we'd ask whether \(I\) has a solution \(S\) with \(f(S) \ge k\).

The vertex cover example above is such a decision problem derived from an optimization problem. In the vertex cover problem, we normally look for the smallest possible vertex cover. Here, we only want to know whether the input graph, the input instance \(I\), has a vertex cover of size at most \(20\). Whether this vertex cover has size \(2\), \(11\) or exactly \(20\) is immaterial, as is the exact set of vertices in such a cover. All we want to know is whether a vertex cover of size at most \(20\) exists—we don't need to find it. Similarly, we can ask whether a given graph has a spanning tree of weight at most \(523\) or whether there exists a path between two vertices of length at most \(19.1\). These are the decision versions of the minimum spanning tree and shortest path problems.

Lemma 21.1: If an optimization problem \(\Pi_o\) can be solved in \(T(n)\) time, then its corresponding decision problem \(\Pi_d\) can be solved in \(O(T(n))\) time.

Proof: Assume for the sake of concreteness that \(\Pi_o\) is a minimization problem. The argument for a maximization problem is analogous.

Let \(\mathcal{A}\) be an algorithm that solves \(\Pi_o\) in \(T(n)\) time. We make the reasonable assumption that this output consists not only of the optimal solution \(S\) for the input \(I\) but also includes its objective function value \(f(S)\).

An algorithm \(\mathcal{A}'\) that solves \(\Pi_d\) can be obtained as follows: Given an instance \((I, k)\) of \(\Pi_d\), we run \(\mathcal{A}\) on \(I\). This takes \(T(n)\) time. Let \(S\) be the solution produced by \(\mathcal{A}\), and let \(f(S)\) be its objective function value. To decide whether \((I, k)\) is a yes-instance, we simply compare \(f(S)\) with \(k\) and answer yes if and only if \(f(S) \le k\). This takes constant time.

Overall, the running time of the algorithm is \(T(n) + O(1) = O(T(n))\). The correctness of the algorithm follows from the observation that \(I\) has a solution \(S'\) with \(f(S') \le k\) if and only if an optimal solution \(S\) of \(I\), such as the solution produced by \(\mathcal{A}\), satisfies \(f(S) \le k\). ▨

Lemma 21.1 implies in particular that if there exists a polynomial-time algorithm that solves \(\Pi_o\), then there also exists a polynomial-time algorithm that solves \(\Pi_d\). To prove that an optimization problem we want to solve is hard, we are usually interested in the contrapositive: If there is no polynomial-time algorithm that solves \(\Pi_d\), then there does not exist a polynomial-time algorithm that solves \(\Pi_o\) either.

The second observation is that decision problems are equivalent to formal languages: Any formal language \(\mathcal{L}\) over some alphabet \(\Sigma\) gives rise to a decision problem \(\Pi_\mathcal{L}\): Given a string \(\sigma \in \Sigma^*\), decide whether \(\sigma \in \mathcal{L}\). Conversely, any decision problem \(\Pi\) can be translated into a formal language \(\mathcal{L}_\Pi\): We choose some encoding of the input instances of the problem $\(Pi\) over some alphabet \(\Sigma\). For example, if we want to solve the problem using a real computer, the computer needs to store the input \(I\) in memory, which means it encodes \(I\) as a binary string \(\sigma_I\). The language \(\mathcal{L}_\Pi\) is then the language of all strings \(\sigma_I\) that encode yes-instances.

This equivalence between decision problems and formal languages gives us a clean model to study the computational difficulty of decision problems. For example, recall from CSCI 3136 that a formal language can be decided by a DFA (the corresponding decision problem can be solved by a DFA) if and only if it is regular.