Existence of an algorithm versus knowing it

Question

In theoretical computer science, I often encountered a formulation "there exists a (polynomial) algorithm, that computes..." and in the proof, the algorithm was actually described. So, in fact, the proof contains more that just "existence".

My question is the following: is there any problem for which there is known that an algorithm exists with certain computational complexity, but the proof is non-constructive and no actual algorithm is (possibly) known?

After edit @errorist and @Bressan: Thanks for the idea of a reduction from any open problem in mathematics to an algorithm, right. But I still was looking for some more "typical" problems in computer science, some theorem of the kind "Matrix multiplication can be done in $O(n^{2.1})$ but no algorithm is known" or something like that. Maybe you can help me to formalize what I mean.

Answer 1

Consider the function $f\colon \mathbb{N} \to \{0, 1\}$ defined by $$f(x) = \begin{cases} 1 & \text{if $P$ holds} \\ 0 & \text{otherwise} \end{cases}$$ where $P$ is a currently unsolved problem, for example Goldbach's conjecture.

Then, you can prove that there exists a constant-time algorithm computing $f$: indeed, if $P$ holds the algorithm simply returns $1$, otherwise it simply returns $0$.

But if we knew an algorithm that computes such function, we would also be able to prove or disprove $P$, simply executing it on any input.

Answer 2

This is similar in flavour to your question, but it doesn't relate to computational complexity.

Rice's Theorem states, broadly, that for any nontrivial property of partial functions $\mathbb{N} \to \mathbb{N}$, it is in general uncomputable to determine whether or not a given Turing machine induces a partial function with that property.

There is a "nearly constructive" proof in the sense that if we know of a machine with property $P$ and a machine without $P$, then we can construct an explicit example of a machine whose $P$-ness is uncomputable. However, Rice's theorem itself tells us that it is in general impossible to find such a pair of machines, even though the pair does exist.

Answer 3

Consider the following problem,

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

*Note that here $0^n$ means $n$-fold concatenation, e.g., $0^3 = 000$.

In a computer science post, JeffE shows that $f$ is computable, i.e. there is an algorithm that solves this problem. Note that you cannot simply check if $0^n$ occurs in $\pi$ by traversing digits of $\pi$, because if it does not your algorithm will never halt.

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.

Answer 4

Oh, I finally found such a problem. Here, in this video, Donald Knuth talks about such a problem. It turns out that he actually found the algorithm. But for a day, he knew that there has to be an efficient algorithm, but he did not know what it was.

Steve Cook had proved a very amazing theorem. He said if... if you could... if you took a kind of... a certain kind of computer that is very limited in its capability, and if you could write a program for that dumb kind of computer to solve a problem, no matter how slow that program was then there was a fast way to write a program for a real computer. So, in other words if you take a... a particular limited computer and if it... if it can solve a problem at all then there's a fast way to do it on a real computer. So one of the problems that we... that we could solve with that... with this... with this funny computer was to decide whether a string of letters was a palindrome, whether or not it read the same backward... backward to forward... no, sorry, was a... was a concatenation of... of palindromes... palindrome followed by another palindrome and so on. It was just a curiosity, I mean nobody really cares about concatenation of palindromes but there it was, and... and so according to Cook's theorem, since there was a way for this funny machine to... to recognise these... these palindromes, then there must be a fast way to recognise these... these concatenations of palindromes on a regular computer. But I couldn't think of any good way to do it on a regular computer, it just seemed to me that that was going to be a much harder problem. So, I thought I... I was a pretty good programmer but here is this theorem saying there's a way to do it and I can't think of the way to do it. That's the first time that I was sort of stumped this way by saying that somebody saying that he had a good way and I couldn't think of it.