The complexity class promise-BPP
Defintion
To even define promise-BPP loosely, we first need to define a promise problem.
The idea behind a promise problem is that sometimes running an algorithm on an input or even asking if some input has a desired property only makes sense if we restrict our attention to certain inputs. If we have an algorithm that does something like marriage matching, we don't really care nor expect a sensible answer if we run our algorithm on something other than a bipartite graph.
Formally, a promise problem is a partition of the set of all strings into three classes. The first class is the set of all strings that have the desired property (we'll denote this class by [math]\displaystyle{ \Pi_1 }[/math]), the second is the set of all strings without the desired property (denoted by [math]\displaystyle{ \Pi_0 }[/math]), and the last is the set of all strings that are considered to neither have nor not have the desired property.
Whereas BPP was a set of problems, promise-BPP is a set of promise problems. Now a promise problem lies in the complexity class promise-BPP if and only if there exists an algorithm [math]\displaystyle{ A }[/math] that can take in any string and outputs either 0 or 1 (where we denote the output of our algorithm if we feed it input [math]\displaystyle{ x }[/math] with [math]\displaystyle{ A(x) }[/math]) and has the following properties:
- [math]\displaystyle{ A }[/math] runs in polynomial time for any input
- If [math]\displaystyle{ x \in \Pi_1 }[/math], then [math]\displaystyle{ Pr[A(x)=1]\geq \frac{2}{3} }[/math]
- If [math]\displaystyle{ x \in \Pi_0 }[/math], then [math]\displaystyle{ Pr[A(x)=0]\geq \frac{2}{3} }[/math]
To emphasize, for any [math]\displaystyle{ x \notin \Pi_0 \cup \Pi_1 }[/math], the probability that [math]\displaystyle{ A(x) }[/math] is 1 can be anything, but we know the algorithm always calculates [math]\displaystyle{ A(x) }[/math] quickly.
If we restrict our space of words to [math]\displaystyle{ \Pi_0 \cup \Pi_1 }[/math] (which is called the promise of our promise problem) and restrict our algorithm [math]\displaystyle{ A }[/math] to that set, then our new restricted problem lies in BPP. The problem is we can't always just consider this restriction. There might not be an efficient way to determine if a string is actually in the promise [math]\displaystyle{ \Pi_0 \cup \Pi_1 }[/math]. An example would be if we let the set of all strings be the natural numbers, the promise be the set of all semiprimes, and [math]\displaystyle{ A }[/math] tries to determine if the difference between the two prime factors in a semiprime is a power of two. We can't efficiently tell if a natural number is semiprime, so even though theoretically we could restrict our attention to just semiprimes and speak in terms of BPP, practically we can't do that so this problem lies more naturally in promise-BPP.
External Links
On Promise Problems (a survey in memory of Shimon Even) by Oded Goldreich
