Summary: This post highlights the need for results in AI safety, such as debate or scalable oversight, to 'relativise', i.e. for the result to hold even when all parties are given access to a black box 'oracle' (the oracle might be a powerful problem solver, a random function, or a model of arbitrary human preferences). Requiring this relativisation can often significantly change the complexity class associated with a given protocol and therefore the promise of a given method. We present a few examples of this change and the solutions required to restore the methods back to full power.

Goal: self-contained intuition

This is a purely expositional post describing some of the intuition for why we need relativisation to apply interactive proof techniques to AI safety, and what that does to the necessary proof systems. No new research results, but I previously hadn’t written this story down in a clean way, so now I have something to point to.

Interactive proof systems and IP = PSPACE

An interactive proof system consists of a verifier $V$ and one or more provers $P$ , such that the provers are trying to convince the verifier of answers to questions (formally, usually membership of strings $x$ in some language $L$ ). The simplest proof system is the non-interactive one: a single prover produces a proof string $y = P (x)$ , and the verifier checks the proof as $V (x, y)$ . This corresponds to the complexity class $N P$ .

There are more complicated proof systems, reaching much higher complexity classes. With polynomially many rounds of interaction, a single prover can reach the complexity class $P S P A C E$ , which is the celebrated result IP = PSPACE ( $I P$ = interactive proofs). However, this result requires re-coding the input problem as a statement about polynomials over finite fields, then using randomness to do polynomial identity testing in the finite field case. For example, if our $P S P A C E$ problem is the alternating Boolean circuit $\exists x_{0} \forall y_{0} \dots \exists x_{m} \forall y_{n} ϕ (x, y)$ where $ϕ (x, y)$ is a circuit, we form an interactive proof by replacing $x \land y \to x y, x \lor y \to 1 - (1 - x) (1 - y)$ , etc. (and doing some trickery to lower degrees, which I will ignore for this sketch). The prover then makes claims about what the summary polynomials are if we marginalise over some suffix of the variables. If the finite field is large enough, a single randomly chose...

Posts

Wikitag Contributions

Comments