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$
0

2 Answers 2

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.

$\endgroup$
9
  • $\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$ Dec 16, 2019 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$ Dec 16, 2019 at 18:39
  • $\begingroup$ I don't think so. See my updated answer. $\endgroup$ Dec 16, 2019 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$ Dec 16, 2019 at 19:29
  • $\begingroup$ In your argument, I don't see how you get that some $P$ occurs infinitely often. $\endgroup$ Dec 16, 2019 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$.

$\endgroup$
8
  • $\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$ Dec 18, 2019 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, 2019 at 9:58
  • $\begingroup$ Can you explain what you mean by "run all of them"? $\endgroup$ Dec 18, 2019 at 9:58
  • $\begingroup$ @YuvalFilmus Run all $P_i$s in the same time. Can be simulated in $P$ $\endgroup$
    – l4m2
    Dec 18, 2019 at 10:01
  • $\begingroup$ What do you mean by “all $P_i$”? $\endgroup$ Dec 18, 2019 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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