Non-constructive algorithm existence proofs

The vast majority of positive results about computational problems are constructive proofs. I.e., a computational problem is proved to be solvable by showing an algorithm that solves it; a computational problem is shown to be in P (complexity) by showing an algorithm that solves it in time that is polynomial in the size of the input; etc.

However, there are several rare non-constructive results, where an algorithm is proved to exist without showing the algorithm itself.

Finite sets

A simple example of a function having a non-constructive algorithm is:

Let f be the following constant function:

f=1 if Goldbach's conjecture is true;

f=0 otherwise.

Goldbach's conjecture is either true or false. If it is true then f is 1, and the required algorithm is just "print 1". If it is false then the required algorithm is just "print 0". In either case, there is a simple, one-line algorithm that prints f, so by definition, f is computationally decideable. It is true that we don't know which algorithm to use, but we do know that an algorithm exists.

A slightly more complicated example is:

Let

$\qquad \displaystyle f(n)={\begin{cases}1&0^{n}{\text{ occurs in the decimal representation of }}\pi \\0&{\text{else}}\end{cases}}$

The function f is computable because there are only two possibilities to consider:

• For every positive integer n, the string $0^{n}$ appears in the decimal representation of $\pi$. In this case, the algorithm that always returns 1 is always correct.
• There is a largest integer N such that $0^{N}$ appears in the decimal representation of $\pi$. In this case the following algorithm (with the value $N$ hard-coded) is always correct:

Zeros-in-pi(n):

if (n > N) then return 0 else return 1

We have no idea which of these possibilities is correct, or what value of N is the right one in the second case. Nevertheless, one of these algorithms is guaranteed to be correct. Thus, there is an algorithm to decide whether a string of n zeros appears in $\pi$; the problem is decidable.

Membership of graph in family

Some more useful existence proofs can be found in graph theory. A common question in graph theory is whether a certain input graph belongs to a certain family of graphs. For example:

Input: a graph G.

Question: Can G be embedded in a 3-dimensional space, such that no two disjoint cycles of G are topologically linked (as in links of a chain)?

There is a highly exponential algorithm that decides whethet two cycles embedded in a 3d-space are linked, and one could test all pairs of cycles in the graph, but it is not obvious how to account for all possible embeddings in a 3d-space. Thus, it is a-priori not clear at all if the linkedness problem is decideable.

However, there is a non-constructive proof that shows that linkedness is decideable in polynomial time. The proof relies on the following facts:

• The set of graphs for which the answer is "yes" is closed under taking minors. I.e., if a graph G can be embedded linklessly in 3d-space, then every minor of G can also be embedded linklessly.
• For every two graphs G and H, it is possible to find in polynomial time whether H is a minor of G.
• By Robertson–Seymour theorem, any set of finite graphs contains only a finite number of minor-minimal elements. In particular, the set of "yes" instances has a finite number of minor-minimal elements.

Given an input graph G, the following "algorithm" solves the above problem:

For every minor-minimal element H:

If H is a minor of G then return "yes".

return "no".

The non-constructive part here is the Robertson–Seymour theorem. Although it guarantees that there is a finite number of minor-minimal elements it does not tell us what these elements are. Therefore, we cannot really execute the "algorithm" mentioned above. But, we do know that an algorithm exists and that its runtime is polynomial.

There are many more similar problems whose decidability can be proved in a similar way. In some cases, the knowledge that a problem can be proved in a polynomial time has lead researchers to search and find an actual polynomial-time algorithm that solves the problem in an entirely different way. This shows that non-constructive proofs can have constructive outcomes.

See also

• Pure existence theorem