2
$\begingroup$

Wikipedia defines BPP as follows:

Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic Turing machine M, such that

  1. M runs for polynomial time on all inputs
  2. For all x in L, the fraction of strings y of length $p(|x|)$ which satisfy $M(x, y) = 1$ is greater than or equal to 2/3
  3. For all x not in L, the fraction of strings y of length $p(|x|)$ which satisfy $M(x, y) = 1$ is less than or equal to 1/3

I'm wondering if there are any classes that relax the "all inputs" in (2) and (3) to "most inputs". That is, what if we say "For at least 2/3 of the strings x in L" and "For at least 2/3 of the strings x not in L" (or numbers other than 2/3)? (Or perhaps we have to say: for every length n, 2/3 of the strings x of length n...)

For example, do we know whether or not it's the case that SAT falls into some such class, where we may be able to write a randomized polynomial-time algorithm that can correctly answer SAT or UNSAT for a large fraction of inputs, but might always be incorrect (regardless of random seed) for some small fraction of cases? Is there existing literature on this sort of question?

This question can also be generalized to other complexity classes. For example, do we know whether or not there exist always-terminating algorithms, and that can correctly decide the halting problem for a fixed positive fraction of Turing machines of any description length?

$\endgroup$
2
  • 3
    $\begingroup$ These kind of things are called heuristic classes. See e.g. complexityzoo.net/Complexity_Zoo:H#heurbpp . $\endgroup$ May 8, 2023 at 6:08
  • $\begingroup$ I thought there's usually an issue with these kinds of setups due to padding arguments and/or encoding choices (e.g. the answer for SAT might change based on how you write a SAT instance?). Looks like the heuristic classes make the failure fraction 1/poly small - maybe related. $\endgroup$
    – usul
    May 10, 2023 at 2:57

0

Your Answer

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