<p>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.</p>

CC BY-SA 4.0
2021-10-17T02:58:57.687Z
How about the problem "Given an integer $x$, determine whether or not there exists an integer $y>x$ such that $y$ is the Godel numbering of a $ZFC$ proof of $\neg \textrm{Con}(ZFC)$." One can show that this can be solved in constant time, but no explicit TM is known to decide the problem at all.
Yonatan N
CC BY-SA 4.0
2021-10-17T07:16:06.693Z
Lower bound on constant and some explanation?
Turbo
CC BY-SA 4.0
2021-10-17T09:00:46.443Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-10-17T11:44:52.220Z
@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.
Yonatan N
CC BY-SA 4.0
2021-10-17T17:42:58.917Z
(That second one should also say $\neg \textrm{Con}(ZFC)$.)
Yonatan N
CC BY-SA 4.0
2021-10-17T21:33:57.177Z
The RS theorem as explained in https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem#Polynomial_time_recognition makes it appear P/O(1) or P/poly rather than P. Can the obstruction be computable in P time as well?
Turbo
CC BY-SA 4.0
2021-10-17T21:35:06.060Z
I guess I do not know the ZFC stuff. The comment provided assumes the reader alrader knows of details.
Turbo
CC BY-SA 4.0
2021-10-19T20:55:21.110Z
@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.
Hermann Gruber
CC BY-SA 4.0
2021-10-19T23:06:26.720Z
Can we get examples in circuit complexity? I guess that Adelman's theorem implies existence of small circuits for e.g. polynomial identity testing, where we don't know how to constructively generate circuits that small (in polynomial time).
usul
CC BY-SA 4.0
2021-10-20T01:14:58.510Z
@hermanngruber still sounds p/poly.
Turbo
CC BY-SA 4.0
2021-10-20T10:53:31.083Z
@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).
Emil Jeřábek
CC BY-SA 4.0
2021-10-20T12:49:05.290Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-10-20T17:13:49.483Z
Neither the wiki nor your description originally made sense. I still do not understand what you mean by fixed there (is it O(1)) but it's ok. Instead of highbrow writing and explaining your stellar verbose style perhaps you could have made it simple as in 'the obstruction is a list of size O(1) for every minor family and so if list is known for every graph we can decide the property' if that is what is meant. Alright The algorithm appears constructive in any case and so may be a non example. Btw I am aware of p/poly. It is the indirect description here on O(1) list which seemed dependent on n.
Turbo
CC BY-SA 4.0
2021-10-21T20:26:11.303Z
The algorithm damn straight constructive unless you want to get the abnormal satisfaction by providing a ' my answer too' answer.
Turbo
<proofs><complexity>
Any problems for which we know the complexity, but no algorithms with the same time?
MinusPi
# Any problems for which we know the complexity, but no algorithms with the same time?

(Asked by: username_0 on 2021-10-17)

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.

**Tags:** proofs, complexity

> **Comments:**
> **username_1**: How about the problem "Given an integer $x$, determine whether or not there exists an integer $y>x$ such that $y$ is the Godel numbering of a $ZFC$ proof of $\neg \textrm{Con}(ZFC)$." One can show that this can be solved in constant time, but no explicit TM is known to decide the problem at all.  
> **username_2**: Lower bound on constant and some explanation?  
> **username_3**: 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.  
> **username_1**: @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.  
> **username_1**: (That second one should also say $\neg \textrm{Con}(ZFC)$.)  
> **username_2**: The RS theorem as explained in https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem#Polynomial_time_recognition makes it appear P/O(1) or P/poly rather than P. Can the obstruction be computable in P time as well?  
> **username_2**: I guess I do not know the ZFC stuff. The comment provided assumes the reader alrader knows of details.  
> **username_4**: @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.  
> **username_5**: Can we get examples in circuit complexity? I guess that Adelman's theorem implies existence of small circuits for e.g. polynomial identity testing, where we don't know how to constructively generate circuits that small (in polynomial time).  
> **username_2**: @hermanngruber still sounds p/poly.  
> **username_3**: @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).  
> **username_3**: Rereading the comments, username_2, 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.  
> **username_2**: Neither the wiki nor your description originally made sense. I still do not understand what you mean by fixed there (is it O(1)) but it's ok. Instead of highbrow writing and explaining your stellar verbose style perhaps you could have made it simple as in 'the obstruction is a list of size O(1) for every minor family and so if list is known for every graph we can decide the property' if that is what is meant. Alright The algorithm appears constructive in any case and so may be a non example. Btw I am aware of p/poly. It is the indirect description here on O(1) list which seemed dependent on n.  
> **username_2**: The algorithm damn straight constructive unless you want to get the abnormal satisfaction by providing a ' my answer too' answer.  

---

## 0 answers

