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).

  • $\begingroup$ 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. $\endgroup$ – Tom van der Zanden May 16 '15 at 9:55
  • $\begingroup$ @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'$? $\endgroup$ – babou May 16 '15 at 10:41
  • $\begingroup$ @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. $\endgroup$ – Tom van der Zanden May 16 '15 at 11:42
  • $\begingroup$ It is highly improbable, but whether it can be proved unconditionally, I don't know. $\endgroup$ – 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)$?


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.