Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
A problem in $P$ is one that can be solved in polynomial time (or faster) on a deterministic Turing machine. Now if I am correct, there is nothing here referring to the algorithms - which can themselves can be given a complexity class (necessarily greater or equal to that or the problem).
My question is: Are there any problems in $P$ for which we do not know the existence of any algorithm in $P$.
I am physicist by training so please let me know if anything doesn't make sense.
Nice question! I think the answer is "yes", but I can't prove it.
The answer is not obvious. You might imagine that if we had a problem with a non-constructive proof that it is in $P$, we might know it is in $P$ without knowing of an algorithm for it. For instance, here is a reasonable candidate for such a problem:
$$f(n) = \begin{cases} 1 & \text{if $0^n$ occurs in the decimal representation of } \pi \\ 0 & \text{otherwise.}\end{cases}$$
The problem is to compute $f$.
We can prove that $f$ is in $P$, but as far as I know, we don't know of any specific polynomial-time algorithm that we can prove correctly computes $f$. In other words, we're certain that such an algorithm exists, but we can't write one down that we're sure works. In particular, we know of an infinite family of algorithms, such that all of them run in polynomial time and one of them is correct; but as far as I know, we don't know which one is correct. See How can it be decidable whether $\pi$ has some sequence of digits? for details.
So, I suspect that the answer to your question is "yes" and that $f$ is such an example.
You can find more examples at https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs. That page shows examples of problems where we can prove that a polynomial-time algorithm exists, but that proof is non-constructive, in the sense that it does not tell us what the algorithm is. Now that said, it's possible that this just reflects our lack of current knowledge. Maybe tomorrow someone will come up with a constructive proof that those problems are in P, i.e., maybe they will come up with a specific algorithm that they can prove is correct and runs in polynomial-time. But as it stands today, we don't know of any such algorithm.
See also https://cstheory.stackexchange.com/q/4777/5038, https://cstheory.stackexchange.com/q/12162/5038, and Is there an algorithm that provably exists although we don't know what it is?.
At the same time, there is a limited more limited version of the question for which the answer is "no".
If you limit yourself to problems in NP that have a known nondeterministic polynomial-time algorithm, then we can say that the answer is "no" for those problems: for every problem that is known to be in P and is known to have a nondeterministic polynomial time algorithm, we know of a polytime (deterministic) algorithm for it.
It might sound crazy, but it's true. In particular, one can use Levin universal search to write down an algorithm for such a problem. The resulting algorithm will have constant factors that make it totally impractical, but we can prove it runs in polynomial time and that it is correct. See What is a lay explanation for universal search?, Polytime algorithm for SUBSET-SUM assuming P=NP, and Is there a concept for an algorithm computing a function by first finding another algorithm?.
The classic example is the family of problems related to the Robertson-Seymour Theorem in graph theory.
This result says that any minor-closed class of graphs can be described as the graphs excluding a finite set of minors. However, the proof is non-constructive: the theorem doesn't say what those minors actually are. If we did have the finite set of minors, then the algorithm to decide whether an input graph is in a minor-closed class $C$ would be quite easy, and it is even known that it can be implemented to run in quadratic time.
So we have infinitely many classes of graphs, many quite interesting, for which we know that recognition is in $\textsf{P}$, but we currently have no idea how to construct the recognition algorithm guaranteed by the theorem.
