# Is it possible that low-resource Turing Machines can always “usually” agree with high-resource Turing Machines

Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs.

It is known that there are problems in $TIME(n^{3})$ that are not in $TIME(n^2)$. But is it possible that, for every language $L \in TIME(n^{3})$, there is a $.99$ approximation in $TIME(n^2)$?

I'm also curious about this question with respect to other computational resources: Nondeterminstic Time, Space, and Randomness (although I'm not even sure if there is a BPTIME hierarchy theorem, so it might be hard to answer for randomness).

• In your example, if every problem can be $f$-approximated then it can also be $f^2$-approximated because $L\oplus L'$ is in $TIME(n^3)$ and thus can be $f$-approximated as well. This gives a $f^2$-, or rather a $1-(1-f)^2$-approximation. – Tom van der Zanden May 16 '15 at 9:55
• @TomvanderZanden I would think that since $f\leq 1$, we always have $f^2\leq f$. Hence, when $L$ is a $f$-approximation of $L'$, it is necessarily also a $f^2$-approximation of $L'$. - - - - What is $L\oplus L'$? – babou May 16 '15 at 10:41
• @babou The $f^2$ is technically incorrect, hence the last part of my comment ($1-(1-f)^2$). $L\oplus L'$ is the symmetric difference of the language, so it is the set of inputs on which $L'$ is wrong. This set can be computed in $TIME(n^3)$, and thus $f$-approximated in $TIME(n^2)$. So first using the $f$-approximation for $L$ and then the one for $L\oplus L'$ gives you a $TIME(n^2)$ approximation with less error. – Tom van der Zanden May 16 '15 at 11:42
• It is highly improbable, but whether it can be proved unconditionally, I don't know. – Yuval Filmus May 16 '15 at 14:42

Okay, I realized there's an uninteresting answer to this question via a "slow" diagonalization argument. Let ${M_k}$ be an enumeration of the machines that run in $TIME(n^2)$. Define $\bar{M}$ to be the machine that does the opposite of $M_k$ on all inputs of length $k$. Then $\bar{M}$ is in $TIME(n^{2 + \epsilon})$, but there is no machine in $TIME(n^2)$ that is a $0.001$ approximation of $\bar{M}$, because there is some input length on which the two machines disagree everywhere.
I don't feel like this really captures the spirit of the question, though, and I'm going to try to think about how to re-formalize it. Maybe I want to say something about circuits? Like: is it possible that for all circuits on $n$ input wires, $SIZE(c)$ has a $.99$ approximation of $SIZE(c+1)$?