5
$\begingroup$

Suppose that $F$ is a problem such that for every $n$, there is a program of length $O(1)$, running in polynomial time to $n$, that solves $F$ correctly on all instances of size less than $n$. Can $F$ be solved in polynomial time? That is, does there exist a single polynomial time algorithm that solves $F$ on all instances?

$\endgroup$
4
$\begingroup$

Suppose that $F$ is a problem such that for every $n$, there is a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$.

Let $P_n$ be a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$. Since there are only finitely many programs of length at most $C$, there must be a single program $P$ that occurs infinitely often as $P_n$. This program solves $F$ in polynomial time for all instances.


If we change $O(1)$ to any bound $f(n) = \omega(1)$ computable in $\mathit{poly}(n)$ time, then we can easily construct undecidable problems which are computable in this model. We can assume that $f$ is monotone and has no jumps (otherwise take $g(n) = \min(\max(f(0),\ldots,f(n)),g(n-1)+1)$). For an undecidable $S \subseteq \mathbb{N}$, consider the following language: $$ L = \{ x \in \{0,1\}^* : f(|x|) \in S \}. $$ Since $f$ is monotone, if $|x| \leq n$ then $f(|x|) \leq f(n)$. Hence there is a program of length $f(n) + O(1)$ that solves $L$ correctly on inputs of length at most $n$. Conversely, since $f$ has no jumps, for each $m$ we can find a value $n$ such that $f(n) = m$, and this gives a computable reduction from $S$ to $L$, showing that $L$ is uncomputable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice! What is the largest advice bound for which this argument still works (i.e. there literally "aren't enough programs" to avoid having some program occur infinitely often)? Does it work for any $\mathbf{P}/o(\log n)$? $\endgroup$ – Aaron Rotenberg Dec 16 '19 at 18:08
  • $\begingroup$ I'm pretty sure it does work for $\mathbf{P}/o(\log n)$. The number of possible programs for $P_n$ is $2^{o(\log n)}$. For any $k$, we have $2^{o(\log n)} < n/k$ for sufficiently large $n$. So for any $k$, there exists an $n$ such that there is some $P$ where at least $k$ positions $i < n$ have $P_i = P$. This implies that some $P$ occurs infinitely often. $\endgroup$ – Aaron Rotenberg Dec 16 '19 at 18:39
  • $\begingroup$ I don't think so. See my updated answer. $\endgroup$ – Yuval Filmus Dec 16 '19 at 18:43
  • $\begingroup$ I'm looking at your proof that it doesn't work and my proof that it does work and they both look right. That probably means mine is wrong, but I don't see why. 😒 $\endgroup$ – Aaron Rotenberg Dec 16 '19 at 19:29
  • $\begingroup$ In your argument, I don't see how you get that some $P$ occurs infinitely often. $\endgroup$ – Yuval Filmus Dec 16 '19 at 19:35
0
$\begingroup$

Let $\{P_i\}$ be the limits of programs, or to say, programs that appear for infinte times, then all of them solve $F$, and for each $size(x)$ at least one solve in $P$.

Now run all of them and use the eariest result, and we get a solution in $P$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This idea (reminiscent of Levin's optimal algorithm) only works if you can verify solution. Otherwise, it could be that $P_i$ solves the problem correctly, and $P_j$ runs $P_i$ and then negates the result. $\endgroup$ – Yuval Filmus Dec 18 '19 at 9:55
  • $\begingroup$ @YuvalFilmus Since $P_j$ appears for infinite times, it solves correctly when size is smaller than a large $n$, so it solves this size correctly, but just maybe slow $\endgroup$ – l4m2 Dec 18 '19 at 9:58
  • $\begingroup$ Can you explain what you mean by "run all of them"? $\endgroup$ – Yuval Filmus Dec 18 '19 at 9:58
  • $\begingroup$ @YuvalFilmus Run all $P_i$s in the same time. Can be simulated in $P$ $\endgroup$ – l4m2 Dec 18 '19 at 10:01
  • $\begingroup$ What do you mean by “all $P_i$”? $\endgroup$ – Yuval Filmus Dec 18 '19 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.