Unconditional derandomization of Arthur-Merlin games

Unconditional derandomization of Arthur-Merlin games

Definitions and mathematical statement

For a language $L\subseteq\{0,1\}^*$, membership in $\mathrm{AM}$ means there is a polynomial-time Boolean verifier $V(x,r,y)$, with $r,y$ of polynomially bounded lengths, such that \[ x\in L\Rightarrow\Pr_r[\exists y\ V(x,r,y)=1]\ge2/3, \qquad x\notin L\Rightarrow\Pr_r[\exists y\ V(x,r,y)=1]\le1/3. \] Here $r$ is uniformly random; Arthur sends $r$ publicly, and Merlin's reply $y$ may depend on it. The polynomial bounds and verifier are fixed for the language.

A language belongs to $\Sigma_2^{\mathrm P}$ when there is a deterministic polynomial-time predicate $W$ and polynomially bounded binary strings $u,v$ such that \[ x\in L\quad\Longleftrightarrow\quad \exists u\ \forall v\ W(x,u,v)=1. \] The question is to establish unconditionally $\mathrm{AM}\subseteq\Sigma_2^{\mathrm P}$. The superscript specifies the second level of the polynomial hierarchy, rather than a level of the arithmetical hierarchy. All machines are uniform and bounds are worst-case polynomial in $|x|$. A simulation using advice, a slower running time, or an additional unproved hardness assumption is not the asserted inclusion. The task asks for this inclusion, not the stronger equality $\mathrm{AM}=\mathrm{NP}$.

Short English statement

Can every Arthur–Merlin language be expressed unconditionally by one polynomially bounded existential block followed by one universal block and an efficient predicate?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 2 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope. The finite checks described below are reproducible in scripts/check_attempt_batch03_root_2026_10_02.py.

Two restricted simulations.

The order of the public randomness and Merlin's response is essential. We prove the desired inclusion when either Arthur's randomness or Merlin's response has logarithmic length. We then display the extra existential block that obstructs extending the same covering argument to the general protocol. The source [S2] asks for an unconditional simulation; a circuit-size assumption on Merlin's strategy would be an additional hypothesis.

Logarithmically many random bits.

Suppose there are $R=2^{O(\log n)}$ possible random strings. An NP certificate lists at least $\lceil2R/3\rceil$ distinct random strings, each with an accepting Merlin response. The verifier checks distinctness and runs the original deterministic verifier on each listed pair. On a yes instance, completeness guarantees enough accepting random strings and responses. On a no instance, at most $R/3$ random strings have any accepting response, so no such certificate exists. The table and its verification have polynomial size. Thus this class of protocols is in NP, and in particular in $\Sigma_2^{\mathrm P}$. This argument guesses the responses; it does not assert that they can be found deterministically in polynomial time.

Logarithmically many response bits.

If instead Merlin's reply has length $O(\log n)$, then for each random string $r$ one can enumerate all replies and compute $B(x,r)=\bigvee_y V(x,r,y)$ deterministically in polynomial time. This produces a BPP computation. For completeness, we give the covering proof of the required $\Sigma_2^{\mathrm P}$ simulation. Repeat the computation independently and take a majority. Its error falls exponentially in the number of repetitions, whereas the total random length $m$ grows only linearly in that number. For example the error from independent trials with error at most $1/3$ is bounded by $(2\sqrt2/3)^N$ after $N$ trials, by applying Markov's inequality to $2^{\text{number of errors}}$. Polynomially many repetitions therefore achieve error $\varepsilon<1/(2(m+1))$ and $\varepsilon\le1/4$; finitely many small inputs can be handled separately.

Let $A_x$ be the accepting subset of $\{0,1\}^m$ for this amplified deterministic predicate, and put $k=m+1$. On a yes input its density is at least $1-\varepsilon$. Choose $k$ independent uniform shifts $a_i$. For any fixed $r$, the probability that no $r\mathbin\oplus a_i$ belongs to $A_x$ is at most $\varepsilon^k$. The expected number of uncovered $r$ is at most $2^m\varepsilon^k<1$, so some shifts cover the whole cube. On a no input the union of any $k$ translates has size at most $k\varepsilon2^m<2^m$, so no shifts cover. Membership is therefore equivalent to \[ \exists a_1,\ldots,a_k\ \forall r\quad \bigvee_{i=1}^k B'(x,r\mathbin\oplus a_i), \] where $B'$ is the amplified polynomial-time predicate. Both quantified blocks have polynomial length, proving the desired inclusion for this restricted protocol family.

Why the general substitution fails.

In a general AM protocol, deciding whether a random string is accepting means deciding $\exists y\,V(x,r,y)$; the response cannot be enumerated in polynomial time. Substituting it in the same covering formula yields \[ \exists(a_i)_i\ \forall r\ \exists(i,y)\quad V'(x,r\mathbin\oplus a_i,y). \] The last existential block depends on $r$ and cannot simply be moved in front of it. Listing a response for each possible $r$ would use an exponential-size table. Guessing a polynomial-size circuit for those responses would require an unproved bound on the complexity of a successful Merlin strategy. Thus the argument has not constructed the polynomial deterministic matrix required for a two-block simulation.

Verification and final status.

The root script exhaustively checks the translate covering assertion on cubes through dimension three, as a finite check on the quantifier direction. The probabilistic calculation proves the general covering lemma. The two logarithmic restrictions are established, while the full unconditional AM inclusion remains unresolved by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3404 (OPG-454), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Unconditional derandomization of Arthur-Merlin games. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/unconditional_derandomization_of_mathcal_am.