<p>Wikipedia defines BPP as follows:</p>
<blockquote>
<p>Alternatively, <strong>BPP</strong> can be defined using only deterministic Turing machines. A language <em>L</em> is in <strong>BPP</strong> if and only if there exists a polynomial <em>p</em> and deterministic Turing machine <em>M</em>, such that</p>
<ol>
<li><em>M</em> runs for polynomial time on all inputs</li>
<li>For all <em>x</em> in <em>L</em>, the fraction of strings <em>y</em> of length <span class="math-container">$p(|x|)$</span> which satisfy <span class="math-container">$M(x, y) = 1$</span> is greater than or equal to 2/3</li>
<li>For all <em>x</em> not in <em>L</em>, the fraction of strings <em>y</em> of length <span class="math-container">$p(|x|)$</span> which satisfy <span class="math-container">$M(x, y) = 1$</span> is less than or equal to 1/3</li>
</ol>
</blockquote>
<p>I'm wondering if there are any classes that relax the &quot;all inputs&quot; in (2) and (3) to &quot;most inputs&quot;.  That is, what if we say &quot;For at least 2/3 of the strings <em>x</em> in <em>L</em>&quot; and &quot;For at least 2/3 of the strings <em>x</em> not in <em>L</em>&quot; (or numbers other than 2/3)?  (Or perhaps we have to say: for every length <em>n</em>, 2/3 of the strings <em>x</em> of length <em>n</em>...)</p>
<p>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?</p>
<p>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?</p>

CC BY-SA 4.0
2023-05-08T06:08:15.220Z
These kind of things are called *heuristic* classes. See e.g. https://complexityzoo.net/Complexity_Zoo:H#heurbpp .
Emil Jeřábek
CC BY-SA 4.0
2023-05-10T02:57:33.533Z
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.
usul
<cc.complexity-theory><complexity-classes>
Variants of complexity classes that allow "adversarial inputs"?
Jason Gross
# Variants of complexity classes that allow "adversarial inputs"?

(Asked by: username_0 on 2023-05-07)

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?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: These kind of things are called *heuristic* classes. See e.g. https://complexityzoo.net/Complexity_Zoo:H#heurbpp .  
> **username_2**: 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.  

---

## 0 answers

