Promise Problems: Connections Between Derandomization And Complexity Classes

Promises and Derandomization

A promise problem is a generalization of a language or decision problem where the input is promised to have certain properties. More formally, a promise problem P contains two disjoint sets P_yes and P_no, and an input x is promised to be in either P_yes or P_no. A correct algorithm for P must accept all inputs in P_yes and reject all inputs in P_no. The sets P_yes and P_no represent a promise on the input distribution.

Derandomization in complexity theory refers to the removal or reduction of randomness from probabilistic algorithms and complexity classes like BPP and BQP. A key goal is to obtain deterministic polynomial-time algorithms for problems with fast randomized solutions. Promise problems have emerged as an important tool for obtaining unconditional derandomization results by making promises on the input distribution.

Definition of promise problems

Formally, a promise problem P = (P_yes, P_no) consists of disjoint sets P_yes, P_no ⊆ {0,1}^* representing yes- and no- instances. An algorithm solves P if it accepts all x ∈ P_yes and rejects all x ∈ P_no. The sets P_yes and P_no represent a promise that the input x comes from either P_yes or P_no. Unlike languages, it is allowed for an algorithm to output anything on inputs outside P_yes ∪ P_no.

Table of Contents

Connections with probabilistically checkable proofs

There are deep connections between the theory of promise problems and probabilistically checkable proofs (PCPs). PCPs provide short proofs that can be verified by reading only a few bits of the proof in a randomized fashion. The PCP Theorem states that NP = PCP[log n, 1]. Constructing PCPs relies heavily on manipulating promise problems.

For example, the gap versions of constraint satisfaction problems form an important class of promise problems in PCP constructions. We restrict yes- and no- instances to have constraints either almost all satisfiable or almost all unsatisfiable. The promise gap allows the verifier to distinguish these cases easily with few random checks.

Implications for derandomization

Promise problems have led to major derandomization results like removing randomness from polynomial-time algorithms. For example, the PCP Theorem directly implies that promise-BPP = promise-P by using error-correcting codes in the PCP to derandomize the BPP machine. This derandomization holds under the promise gap between yes- and no- instances.

Promise problems also enable unconditional derandomization results using hardness assumptions. For example, we can show that promise-BPP = promise-P relative to an oracle under assumptions like NP ⊈ P/poly. Here the promise gap allows us to “simulate” randomized algorithms with NP hardness as a resource.

Promise BPP vs promise BQP

Promise-BPP and promise-BQP are promise problem analogues of the randomized complexity classes BPP and BQP. An important open question is whether quantum computers can solve promise problems faster than classical computers, i.e. does promise-BQP ⊊ promise-BPP hold?

Promise-BPP definition

A promise problem P = (P_yes, P_no) is in promise-BPP if there is a polynomial-time probabilistic Turing machine M such that:

If x ∈ P_yes, then Pr[M(x) = 1] ≥ 2/3
If x ∈ P_no, then Pr[M(x) = 0] ≥ 2/3

So M solves the promise problem with good probability in polynomial time given the promise on the input distribution.

Promise-BQP definition

Promise-BQP is defined analogously, but with M being a polynomial-time quantum Turing machine. Hence promise-BQP captures the power of quantum computers for promise problems. An open question is whether quantum computers offer an advantage:

Promise-BQP ⊆ Promise-BPP ?

Partial results

Some evidence that promise-BQP may exceed promise-BPP comes from quantum algorithms for promise versions of group theory problems. For example, the quantum algorithm of Watrous for testing solvability of groups runs exponentially faster than known classical algorithms under a promise gap.

But fully establishing an unconditional separation remains elusive. Relative to an oracle, there exist promise problems in PromiseBQP that require exponential time on classical computers. But removing the reliance on an oracle is a major open problem.Sample code: promise gap decoding problem

Here is Python code for a simple promise gap decoding problem. The input consists of a binary codeword x of length n bits with either at most d/10 fraction of bits flipped, or at least d/2 bits flipped from some original codeword. The goal is to correct up to d/2 errors to recover the original codeword:


import random

# generate random binary codeword  
def generate_codeword(n):
  return [random.randint(0,1) for _ in range(n)]

# flip d random bits to simulate errors
def flip_bits(codeword, d):
  result = codeword[:]
  positions = random.sample(range(len(codeword)), d)
  for p in positions:
    result[p] = 1 - result[p] 
  return result

n = 100 # codeword length
d = 10 # number of errors

# generate original codeword
original = generate_codeword(n) 

# flip d/10 bits 
x1 = flip_bits(original, d//10) 

# flip d/2 bits
x2 = flip_bits(original, d//2)

# solve promise problem:
# correct if at most d/10 errors, output FAIL if at least d/2 errors
def solve_promise_problem(y):
  num_errors = sum(y[i] != original[i] for i in range(n))
  if num_errors <= d//10:
    return original
  elif num_errors >= d//2:
    return "FAIL"
  else:
    return "UNDEFINED"

print(solve_promise_problem(x1)) # corrects small errors 
print(solve_promise_problem(x2)) # reports FAIL

This code demonstrates using the promise gap to simplify decoding. The algorithm only needs to correct up to d/2 errors or detect over d/2 errors, allowing efficient recovery and detection.

Open problems and future research directions

Promise problems occupy an exciting frontier in complexity theory and derandomization. Here are some open problems for future work:

Prove an unconditional separation between promise-BPP and promise-BQP
Resolve the relation between promise-BPP and deterministic exponential time classes like promise-EXP
Construct promise problems requiring exponential size PCPs, implying better hardness of approximation results
Study applications of promise problems in areas like algorithm design, quantum computation, and learning theory
Relate promise problems to other models like interactive proofs and probabilistically checkable proofs

The theory of promise problems links many central areas spanning complexity theory, algorithms, cryptography, quantum computing, and more. Continuing progress on promise problems offers exciting prospects for new derandomization, hardness, and algorithmic results.