Structural Complexity of Rational Interactive Proofs
Daniil Musatov1,2 and Georgii Potapov1
1 Moscow Institute of Physics and Technology
2 Caucasus Mathematical Center at Adyghe State University

Computability in Europe 2023
July 25th , Batumi, Georgia

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

1 / 19

Introduction

In 2012, P. D. Azar and S. Micali introduced a new model of interactive
proofs, called “Rational Interactive Proofs”. In this model the prover isneither honest nor malicious, but rational in terms of maximizing his
expected reward.
Rational interactive proofs provide a model for delegated computations
and cloud computing, but they also introduce new classes that areinteresting from the structural complexity point of view.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

2 / 19

Definition (informal)x

ai ← Upoly(|x|)

m1
a1
m2

AM

mi : ER → max⇓
π = I(x ∈ A)

a2···
R(x; m1 , a1 , . . . , mk , ak )π(x; m1 , a1 , . . . , mk )Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive ProofsComputability in Europe 2023

3 / 19

Definition (formal)
Definition
Let Σ be a finite alphabet (e.g. Σ = {0, 1}). A protocol of a rational
interactive proof with k rounds is defined by two polynomial timecomputable functions R : Σ∗ → [0, 1], π : Σ∗ → {0, 1}. Let x ∈ Σ∗
be an instance of a problem.
We use symbols a1 , . . . , ak for Verifier’s (Arthur’s) messages andsymbols m1 , . . . , mk for Prover’s (Merlin’s) messages.
Arthur’s messages are chosen uniformly and independently from thesets of strings of length polynomial in |x| (although many of ourresults still hold for the model with private randomness).
We say that the word x is accepted by the protocol if
π(x; m1 , a1 , . . . , ak−1 , mk ) = 1.
We say that the value R(x; m1 , a1 , . . . , mk , ak ) is the reward
computed for the transcript T = (x; m1 , a1 , . . . , mk , ak ).
Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

4 / 19

Rational Merlin and rational proofs
Definition
When talking about the protocol defined by functions R and π, we saythat Merlin is rational, if m1 , . . . , mk satisfy the following condition:
mi+1 ∈ Argmaxm Eai+1 max . . . max Eak R(x; m1 , . . . , ai , m, ai+1 , . . . , mk , ak ),
mi+2

mk

in other words, in each round, Merlin chooses his message in a way thatmaximizes the expected reward.

Definition
We say that a rational interactive protocol recognizes set A, if for any x
and any Merlin’s rational behaviour, it holds thatx ∈ A ⇐⇒ π(x; m1 , a1 , . . . , ak−1 , mk ) = 1.
Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

5 / 19Finally, definitions of DRMA[k] and FRMA[k]Definition
Class DRMA[k] is the class of all languages recognised by some k-roundrational interactive protocol.

Definition
Functional class FRMA[k] is defined in a similar manner with decisionpredicate π replaced by an arbitrary polynomial time computablefunction φ. A rational interactive protocol computes f if, for any Merlin’s
rational behavior, it holds that φ(T ) = f (x).

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

6 / 19

Example of a DRMA[1]-protocolReminder
Class PP is the class of all languages L for which there exists a
polynomial p and a polynomial time computable predicate V such thatno
L = x ∈ Σ∗ V (x, y) = 1 for at least half of all y ∈ {0, 1}p(|x|) .
For a language L ∈ PP, consider the following protocol:
π(x; m) = m for Merlin’s message m ∈ {0, 1},R(x; m, a) = I{m = V (x, a)}.

It is easy to see that the rational Merlin will “bet” on the actual majority
among the values of V (x, · ).

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

7 / 19

Example of a FRMA[1]-protocol

Let V be a polynomial time computable predicate like before, and let
f (x) = Er V (x, r). Then f ∈ FRMA[1]. To see this, consider thefollowing protocol:
φ(x; m) = m (here we identify a binary string m with a binary
expansion of a number 0.m1 m2 . . . m|m| ∈ [0, 1]),
2R(x; m, a) = 1 − m − V (x, a) .

Correctness of the protocol follows from the fact that for a randomvariable ξ it holds that Eξ = argminc E(ξ − c)2 .

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

8 / 19Known upper and lower bounds on DRMA[k]Theorem (P. D. Azar and S. Micali, 2012)For all k:
Ck P ⊆ DRMA[k] ⊆ C2k+1 P,
where Ck P is the k-th level of the Counting hierarchy, defined as follows:
C0 P = P, C1 P = PP, Ck+1 P = PPCk P .
For the lower bound, the idea of the proof is that, if an execution of aprotocol Π uses a result obtained in a protocol Π′ , then it is possible toexecute both protocols consequently if the reward for Π is scaled down somuch that no gain in the altered execution of Π can validate any loss inthe expected reward for Π′ . Different variations of this idea are widelyused in many works on rational proofs.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 20239 / 19

“Decomposition” of a rational proof
S. Guo et al. (2015) have studied similar compositions of rational andclassical interactive proofs for a slightly different model. In our work, we
study composition and “decomposition” of two rational proofs.

Lemma
For any integer i, j ≥ 0, for any FRMA[i + j]-protocol Π for computing
function f there exists a function fe that:
1for any x maps any transcript Ti of the first i rounds of interactingwith a rational Merlin according to protocol Π on input x to(EiΠ (Ti ), f (x)),

2maps any transcript Ti of i rounds (i.e. of interaction between Arthur
and an arbitrary prover) to (EiΠ (Ti ), v) for some v,

3is in FRMA[j].

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

10 / 19

Bounds for oracle computations

Theorem
For all i, j ≥ 0, the following inclusions hold:
FRMA[i + j] ⊆ FRMA[i](FRMA[j])[1] ⊆ FRMA[i]||DRMA[j] ,DRMA[i + j] ⊆ DRMA[i](FRMA[j])[1] ⊆ DRMA[i]||DRMA[j] ,where “ [1]” means that only one oracle query is allowed.

RemarkFor the Counting Hierarchy, we have equality: Ci PCj P = Ci+j P.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

11 / 19

Polynomial time computations with DRMA[k]-oracles

Theorem
PDRMA[k] = DRMA[k] for all k.
Applying this theorem we can immediately obtain the following result.

Corollary
PPP ⊆ DRMA[1].
Note that, according to the Toda’s theorem, we have PH ⊆ PPP , but it
is not known whether or not PH is in PP. This makes us believe that theclass DRMA[1] must be wider than PP.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

12 / 19

“Composition” of rational proofs
Using the obtained result on PDRMA[k] , we can also prove the following
technical lemma.

Lemma
If, for some numbers i, j ≥ 0 and a language A there exists a
DRMA[i]FRMA[j] -protocol Π, such that oracle queries in it depend only
on the input string and Arthur’s random bits, but not on Merlin’s
messages, then A ∈ DRMA[i + j].
From this lemma, we can easily obtain the following theorem.

TheoremPPDRMA[k] ⊆ DRMA[k + 1] for all k.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

13 / 19

Other interesting corollaries

Now using the last theorem we can also obtain the following results.

Corollary
PHDRMA[k] ⊆ DRMA[k + 1] for all k.

Corollary
If PPDRMA[k0 ] = DRMA[k0 ] for some k0 , then the Counting Hierarchycollapses to (2k0 + 1)-st level.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

14 / 19

Communication complexity

If for a language L ⊂ Σ∗ there exists a single round rational proof (π, R)
such that for every x there is a rational Merlin’s message of length c(|x|)
for some function c, then we say that L ∈ DRMA[1, c].
The example protocol from the beginning of our presentation shows that
PP ⊆ DRMA[1, 1].
Thus, it is interesting to study the structure of the DRMA[1, c]“hierarchy”.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

15 / 19

Communication complexity of PPTheorem
PP = DRMA[1, O(log n)].
Sketch of the proof :1The problem of comparing the expected rewards of any two possible
messages is in PP;

2

Due to the result by L. Fortnow and N. Reingold (1991), if L istruth-table reducible to some langueage in PP, then the language L
is itself in PP.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

16 / 19

What about ⊕P?

S. Guo et al. (2014) also have studied the communication complexity ofrational proofs. They have obtained a different generalisation of the factthat PP ∈ DRMA[1, 1] and have proven that one bit from Merlin is notenough for sublinear time Arthur to compute the parity of all bits of input,
thus showing that a “scaled-down” version of a ⊕P-problem cannot besolved with 1 bit from a rational Merlin.
Our result on communication complexity of PP shows that asuperlogarithmic lower bound on communication complexity for problemsin ⊕P will result in the separation of PP from ⊕P.

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

17 / 19

Lower bound for ⊕P in a black-box model
Although we were unable to prove such a lower bound, we obtained alinear lower bound on the communication complexity of the protocols that
only use a certificate verificator V from the definition of ⊕P as a random
bit generator.

Theorem
There is no polynomial-time computable functions R : {0, 1}∗ → [0, 1] andφ : {0, 1}∗ → {0, 1} such that for any n and 0 ≤ k ≤ 2n the value ofφ(1n , m∗ ) is equal to the parity of k wherem∗ ∈ Argmaxm Ea,r R(1n , m, a, r), |m∗ | < αn for some constantα ∈ (0, 1), a ∼ Us with s = poly(n) and r ∈ {0, 1}d withd = poly(n) and
bits of r being independently sampled from Bern 2kn .
The idea is that, for fixed n, m, the reward function is a polynomial in theprobability of nonuniform bits being equal to 1. If m is short, then some
two of these polynomials of polynomial degree have to intersect inexponentially many points.
Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

18 / 19

Thank you for your attention!

Daniil Musatov, Georgii Potapov (MIPT)

Rational Interactive Proofs

Computability in Europe 2023

19 / 19