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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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). $\endgroup$– holfCommented Oct 7, 2022 at 11:46
-
3$\begingroup$ This question is very similar to cstheory.stackexchange.com/questions/12162/… . $\endgroup$– Emil JeřábekCommented Oct 7, 2022 at 12:42
Add a comment
|