Exact Versus Approximate

Many combinatorial problems admit exact solutions, and in these cases, we will usually try hard to find them. The from earlier in this chapter is a good example of an exact resultExact results are also called best possible, sharp or tight.. By this statement, we mean that for each pair \(m\) and \(n\) of positive integers, there is a sequence of \(mn\) distinct real numbers that has neither an increasing subsequence of size \(m+1\) nor a decreasing subsequence of size\(n+1\). To see this, consider the sequence \(\sigma\) defined as follows: For each \(i=1,2,\dots,m\), let \(B_i=\{j+(m-1)i:1\le j\le n\}\). Note that each \(B_i\) is a block of \(n\) consecutive integers. Then define a permutation \(\sigma\) of the first \(mn\) integers by setting \(\alpha\lt \beta\) if there exist distinct integers \(i_1\) and \(i_2\) so that \(\alpha\in B_{i_1}\) and \(\beta\in B_{i_2}\). Also, for each \(i=1,2,\dots,m\), set \(\alpha\lt \beta\) in \(\sigma\) when \(1+(m-1)i\le \beta\lt \alpha\le n+(m-1)i\). Clearly, any increasing subsequence of \(\sigma\) contains at most one member from each block, so \(\sigma\) has no increasing sequence of size\(m=1\). On the other hand, any decreasing sequence in \(\sigma\) is contained in a single block, so \(\sigma\) has no decreasing sequence of size \(n+1\).

As another example of an exact solution, the number of integer solutions to \(x_1+x_2+\dots x_r=n\) with \(x_i>0\) for \(i-1,2,\dots,r\) is exactly \(C(n-1,r-1)\). On the other hand, nothing we have discussed thus far allows us to provide an exact solution for the number of partitions of an integer\(n\).

Here's an example of a famous problem that we can only discuss in terms of approximate solutions, at least when the input size is suitably large. For an integer \(n\), let \(\pi(n)\) denote the number of primes among the first \(n\) positive integers. For example, \(\pi(12)=5\) since \(2\), \(3\), \(5\), \(7\) and \(11\) are primes. The exact value of \(\pi(n)\) is known when \(n\le 10^{23}\), and in fact: \[\begin{aligned}\end{aligned}\]

On the other hand, you might ask whether \(\pi(n)\) tends to infinity as \(n\) grows larger and larger. The answer is yes, and here's a simple and quite classic argument. Suppose to the contrary that there were only \(k\) primes, where \(k\) is a positive integer. Suppose these \(k\) primes are listed in increasing order as \(p_1\lt p_2\lt \dots\lt p_k\), and consider the number \(n=1+p_1p_2\cdots p_k\). Then \(n\) is not divisible by any of these primes, and it is larger than \(p_k\), which implies that \(n\) is either a prime number larger than \(p_k\) or divisible by a prime number larger than \(p_k\).

So we know that \(\lim_{n\rightarrow\infty}\pi(n)=\infty\). In a situation like this, mathematicians typically want to know more about how fast \(\pi(n)\) goes to infinity. Some functions go to infinity slowly, such as \(\log n\) or \(\log\log n\). Some go to infinity quickly, like \(2^n\), \(n!\) or \(2^{2^n}\). Since \(\pi(n)\le n\), it can't go to infinity as fast as these last three functions, but it might go infinity like \(\log n\) or maybe \(\sqrt{n}\).

On the basis of computational results (done by hand, long before there were computers), Legendre conjectured in 1796 that \(\pi(n)\) goes to infinity like \(n/\ln n\). To be more precise, he conjectured that \[\begin{aligned}\end{aligned}\] In 1896, exactly one hundred years after Legendre's conjecture, Hadamard and de la Vallée-Poussin independently published proofs of the conjecture, using techniques whose roots are in the Riemann's pioneering work in complex analysis. This result, now known simply as the Prime Number Theorem, continues to this day to be much studied topic at the boundary of analysis and number theory.

Throughout this text, we will place considerable emphasis on problems for which a certificate can be found in polynomial time. This refers to problems for which there is some constant \(c>0\) so that there is an algorithm \(\cgA\) for solving the problem which has running time \(O(n^c)\) where \(n\) is the input size. The symbol \(\cgP\) is suggestive of polynomial.\(\cgP\)polynomial time problems

Perhaps the most famous question at the boundary of combinatorial mathematics, theoretical computer science and mathematical logic is the notoriously challenging question of deciding whether \(\cgP\) is the same as \(\cgN\cgP\). This problem has the shorthand form: \(\cgP=\cgN\cgP\)? Here, we present a brief informal discussion of this problem.

First, we have already introduced the class \(\cgP\) consisting of all yes-no combinatorial problems which admit polynomial time algorithms. The first two problems discussed in this chapter belong to \(\cgP\) since they can be solved with algorithms that have running time \(O(n)\) and \(O(n^3)\), respectively. Also, determining whether a graph is \(2\)-colorable and whether it is connected both admit polynomial time algorithms.

We should emphasize that it may be very difficult to determine whether a problem belongs to class \(\cgP\) or not. For example, we don't see how to give a fast algorithm for solving the third problem (subset sum), but that doesn't mean that there isn't one. Maybe we all need to study harder!

Setting that issue aside for the moment, the class \(\cgN\cgP\)\(\cgN\cgP\)nondeterministic polynomial time problems consists of yesno problems for which there is a certificate for a yes answer whose correctness can be verified in polynomial time. More formally, this is called the class of nondeterministic polynomial time problems. Our third problem definitely belongs to this class.

The famous question is to determine whether the two classes are the same. Evidently, any problem belonging to \(\cgP\) also belongs to \(\cgN\cgP\), i.e, \(\cgP\subseteq\cgN\cgP\), but are they equal? It seems difficult to believe that there is a polynomial time algorithm for settling the third problem (the subset sum problem), and no one has come close to settling this issue. But if you get a good idea, be sure to discuss it with one or both authors of this text before you go public with your news. If it turns out that you are right, you are certain to treasure a photo opportunity with yours truly.