These notes were based of (Goldreich, 2006)

Promise Problems

A promise problem \Pi is a pair of non-intersecting sets \Pi_\mathsf{Yes}, \Pi_\mathsf{No}\subseteq \{ 0, 1\}^*, where \Pi_\mathsf{No}\cap \Pi_\mathsf{Yes}= \emptyset. The set \Pi_\mathsf{No}\cup \Pi_\mathsf{Yes} is called the promise. Intuitively, one may think that whenever an input is presented to an algorithm, we promise it will come from either Yes instances or No instances.

An example of promise problems is that of tolerant property testing. Let \Delta(\mathcal{D}) be the set of all probability distributions over \Omega_{\mathsf{n}} and define a property \Pi to be a subset of \Delta(\mathcal{D}). Define “YES” instances as probability distributions \mathcal{D} such that we have d_\mathtt{TV} (D, \Pi) \leq \alpha. Define “No” Instances probability distributions \mathcal{D} such that d_\mathtt{TV} (D, \Pi) \geq \beta. Here d_\mathtt{TV} (D, \Pi) := \inf_{\pi \in \Pi}d_\mathtt{TV} (D, \pi) i.e. the smallest distance to a distribution \pi that is in \Pi.

\Pi_\mathsf{Yes}= \{ \mathcal{D}\in \Delta(\mathcal{D}): d_\mathtt{TV} (D, \Pi) \leq \alpha \} \Pi_\mathsf{No}= \{ \mathcal{D}\in \Delta(\mathcal{D}): d_\mathtt{TV} (D, \Pi) \geq \beta \}

The Promise: For any testing algorithm that receives as input, samples from \mathcal{D}, is promised that \mathcal{D}\in \Pi_\mathsf{Yes}\cup \Pi_\mathsf{No}.

Classes Of Promise Problems

\mathsf{P}: The class of promise problems that are solvable in deterministic poly time i.e. there exists a PPT algorithm A such that

  • For every x \in \Pi_\mathsf{Yes}, A(x) = 1.
  • For every x \in \Pi_\mathsf{No}, A(x) = 0.

\mathsf{NP}: class of promise problems that have polynomially long proofs of membership that are verifiable in deterministic poly time. i.e there exists a bounded relation R that is recognised1 by a polytime algorithm A such that

  • For every x \in \Pi_\mathsf{Yes}, there exists a w s.t. (x, w) \in R.
  • For every x \in \Pi_\mathsf{No}, for all w we have (x, w) \notin R

\mathsf{BPP}: The class of promise problems that are solvable in random poly time i.e. there exists a PPT algorithm A such that

  • For every x \in \Pi_\mathsf{Yes}, \Pr[A(x) = 1] \geq \frac{2}{3}.
  • For every x \in \Pi_\mathsf{No}, \Pr[A(x) = 0] \geq \frac{2}{3}.

Karp Reduction Among Promise Problems

The promise problems \Pi= (\Pi_\mathsf{Yes}, \Pi_\mathsf{No}) is karp-reducible to \Pi^\prime = (\Pi_\mathsf{Yes}^\prime, \Pi_\mathsf{No}^\prime) if there exists a polynomial time computable function f such that

  • For every x \in \Pi_\mathsf{Yes}, f(x) \in \Pi_\mathsf{Yes}^\prime.
  • For every x \in \Pi_\mathsf{No}, f(x) \in \Pi_\mathsf{No}^\prime.

Examples Of Karp Reductions of promise problems include:

Cook Reduction Among Promise Problems

The promise problems \Pi= (\Pi_\mathsf{Yes}, \Pi_\mathsf{No}) is cook-reducible to \Pi^\prime = (\Pi_\mathsf{Yes}^\prime, \Pi_\mathsf{No}^\prime) if there exists poly-time oracle machine M such that

  • For every x \in \Pi_\mathsf{Yes}, M^{\Pi_\mathsf{Yes}^\prime} = 1.
  • For every x \in \Pi_\mathsf{No}, M^{\Pi_\mathsf{No}^\prime} = 0.

Here M is an oracle such that any query q to M is answered with 1 if q \in \Pi_\mathsf{Yes}^\prime and 0 if q \in \Pi_\mathsf{No}^\prime. Thus M can check membership in \Pi^\prime.

References and Footnotes

Goldreich, O., 2006. On promise problems: A survey. Essays in Memory of Shimon Even 3895, 254–290.