Existence of an algorithm versus knowing it 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.
 A: 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.
A: 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.
A: 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.
A: 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. 

