<p>Most of the time, a problem is shown to be in P by the construction of a polynomial time algorithm. I wonder if there is a natural problem that was proved in P but no explicit algorithm was known?
I'm aware of the Seymour type theorem about excluding graph minors. The hardness lies in we usually do not know the finite family of excluding minors. Once the family is known there is an explicit algorithm, so that doesn't count.</p>

CC BY-SA 4.0
2022-10-07T11:46:17.423Z
Not an answer but related: the universal search algorithm of Levin gives an algorithm in P for SAT only if P=NP, and this algorithm will work only for sufficiently large formulas (for which we have no bound).
holf
CC BY-SA 4.0
2022-10-07T12:42:32.803Z
This question is very similar to https://cstheory.stackexchange.com/questions/12162/are-there-non-constructive-algorithm-existence-proofs .
Emil Jeřábek
<polynomial-time>
Is there a natural problem in P but no polynomial time algorithm is known?
Kai-Yuan Lai 賴開元
# Is there a natural problem in P but no polynomial time algorithm is known?

(Asked by: username_0 on 2022-10-07)

Most of the time, a problem is shown to be in P by the construction of a polynomial time algorithm. I wonder if there is a natural problem that was proved in P but no explicit algorithm was known?
I'm aware of the Seymour type theorem about excluding graph minors. The hardness lies in we usually do not know the finite family of excluding minors. Once the family is known there is an explicit algorithm, so that doesn't count.

**Tags:** polynomial-time
> **Comments:**
> **username_1**: Not an answer but related: the universal search algorithm of Levin gives an algorithm in P for SAT only if P=NP, and this algorithm will work only for sufficiently large formulas (for which we have no bound).  
> **username_2**: This question is very similar to https://cstheory.stackexchange.com/questions/12162/are-there-non-constructive-algorithm-existence-proofs .  

---

## 0 answers

