# Any problems for which we know the complexity, but no algorithms with the same time?

I suddenly found myself wondering if there are any problems for which the complexity (time or space or anything else) is proven, say to be O(n^2), but for which the best known algorithms are worse than that, say O(n^3). Would such a situation even be possible? I haven't found much of anything with a search, maybe because I'm struggling to word it efficiently.

• Any minor-closed family of graphs is decidable in time $O(n^2)$ as a consequence of the Robertson-Seymour theorem. However, this doesn't give an explicit algorithm as the proof is nonconstructive. Even for quite simple families of graphs (e.g., toroidal graphs) no complete list of forbidden minors is known. Commented Oct 17, 2021 at 9:00
• @Mr. One of the following must be true: either there are no proofs of $\neg \textrm{Con}(ZFC)$ or there are infinitely many proofs of $\textrm{Con}(ZFC)$ (consider padding). In either case, the constant-time algorithm is either the trivial "Yes" algorithm or the trivial "No" algorithm. Commented Oct 17, 2021 at 11:44
• @Mr. Imagine Emil's argument as an infinite family of algorithms: each algorithm in the family works with its own hardcoded list of subgraphs, and the algorithms in this family differ only in that list of subgraphs. One of these algorithms has the property that the list of subgraphs is identical to the set of forbidden minors. This is the desired algorithm which computes the correct result on all inputs. Since the Robertson-Seymour proof is nonconstructive, we don't know which of the algorithm(s) in the family is correct, but we know that one of them does the job. Commented Oct 19, 2021 at 20:55
• @Mr. I can’t make sense of your comments. For any fixed computational problem of the form mentioned (i.e., a fixed minor-closed family), there is a fixed finite set of obstructions. This can be hardwired into the algorithm solving this problem. This is in fact quite clearly explained in the Wikipedia article. You seem to be thinking of a different problem where the minor-closed family varies, and some sort of a description of it is given as part of the input. Then it becomes undecidable, unless the description effectively includes a list of forbidden minors (and even then it’s NP-hard). Commented Oct 20, 2021 at 10:53
• Rereading the comments, Turbo, it seems that you are just confused about the definitions of P and P/poly. It is a trivial basic fact that you can hardwire any finite string into a polynomial-time algorithm; formally, if $f$ is a poly-time function, and $c$ is any string, then the function $g$ defined by $g(x)=f((x,c))$ is polynomial-time computable. In contrast to that, P/poly algorithms are defined as having polynomial-size advice, which is an infinite sequence of strings, one for each input length. This cannot in general be hard-wired into the algorithm, as algorithms are finite. Commented Oct 20, 2021 at 12:49