Random Permutations in Computational Complexity

Bennett and Gill [4] initiated the study of random oracles in computational complexity, proving that ${𝖯}^A\ne {\mathrm{𝖭𝖯}}^A$ for a random oracle $A$ with probability 1. Subsequent work extended this to individual random oracles. Book, Lutz, and Wagner [5] showed that ${𝖯}^A\ne {\mathrm{𝖭𝖯}}^A$ for every oracle $A$ that is algorithmically random in the sense of Martin-Löf [17]. Lutz and Schmidt [16] improved this further to show ${𝖯}^A\ne {\mathrm{𝖭𝖯}}^A$ for every oracle $A$ that is pspace-random in the sense of resource-bounded measure [14]. Hitchcock, Sekoni, and Shafei [12] extended this result to polynomial-time betting-game random oracles [6].

The complexity class $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$ is particularly significant because it comprises problems that have both efficiently verifiable proofs of membership and non-membership. This class includes important problems such as integer factorization and discrete logarithm, which are widely believed to be outside $𝖯$ but are not known to be $\mathrm{𝖭𝖯}$-complete. These problems play a central role in cryptography, as the security of widely-used cryptosystems relies on their presumed intractability [22, 7]. Furthermore, under derandomization hypotheses, $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$ has been shown to contain problems such as graph isomorphism [13], further underscoring its importance in complexity theory. Thus, understanding the relationship between $𝖯$ and $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$ relative to different notions of randomness could shed light on the structure of these classes and the limits of efficient computation.

In this work, we develop a novel framework for resource-bounded permutation measure and randomness. We introduce permutation martingales and permutation betting games, extending classical notions of random permutations. Our theory captures essential properties of random permutations while enabling complexity separations. We prove that random oracles can be computed in polynomial time from a random permutation; however, the converse remains unresolved.

First, we recall the basics of resource-bounded measure. A martingale in Cantor space may be viewed as betting on the membership of strings in a language. The standard enumeration of ${\{0,1\}}^{\ast }$ is $s_0=\lambda ,s_1=0,s_2=1,s_3=00,s_4=01,\mathrm{\dots }$. In the $i^{\mathrm{th}}$ stage of the game, the martingale has seen the membership of the first $i$ strings and bets on the membership of $s_i$ in the language. The martingale’s value is updated based on the outcome of the bet. Formally, a classical martingale is a function $d:{\{0,1\}}^{\ast }\to [0,\mathrm{\infty })$ satisfying the fairness condition

for all strings $w$. Intuitively, $d(w)$ represents the capital that a gambler has after betting on the sequence of bits in $w$ according to a particular strategy. The fairness condition ensures that the expected capital after the next bit is equal to the current capital. A martingale succeeds on a language $A\subseteq {\{0,1\}}^{\ast }$ if $\underset{n\to \mathrm{\infty }}{lim\; sup}d(A\upharpoonright n)=\mathrm{\infty }$, where $A\upharpoonright n$ is the length-$n$ prefix of $A$’s characteristic sequence. The success set of $d$ is $S^{\mathrm{\infty }}[d]$, the set of all sequences that $d$ succeeds on. Ville [25] proved that a set $X$ has Lebesgue measure zero if and only if there is a martingale that succeeds on all elements of $X$. Lutz [14] defined resource-bounded measure by imposing computability and complexity constraints on the martingales in Ville’s theorem.

We take a similar approach in developing resource-bounded permutation measure. Unlike a classical martingale betting on the bits of a language’s characteristic sequence, a permutation martingale bets on the function values of a permutation $\pi$. Instead of seeing the characteristic string of a language, a permutation martingale sees a list of permutation function values. More precisely, after $i\ge 0$ rounds of betting, a permutation martingale has seen a prefix partial permutation

where $|g(s_i)|=|s_i|$ for all $i$. The permutation martingale will bet on the next function value $g(s_i)$. The current betting length is $l(g)=|s_i|$, the length of the next string $s_i$ in the standard enumeration. The set of free strings available for the next function value is

For any prefix partial permutation $g$, a permutation martingale $d$ outputs a value $d(g,x)\ge 0$ for each $x\in \mathrm{𝖿𝗋𝖾𝖾}(g)$. The values satisfy the averaging condition

Here $g,x$ denotes appending the string $x$ as the next function value in prefix partial permutation $g$.

Prefix partial permutations may be used as cylinders to define a measure in $\mathsf{\Pi }$ that is equivalent to the natural product probability measure. We detail this in Section 3. Briefly, a class $X\subseteq \mathsf{\Pi }$ has measure 0 if for every $ϵ>0$, there exists a sequence of cylinders $\{⟦g_i⟧\mid i\in \mathbb{N}\}$ that has total measure at most $ϵ$ and covers $X$. This is difficult to work with computationally as the covers may be large and require exponential time to enumerate.

We prove an analogue of Ville’s theorem [25], showing that permutation martingales characterize measure 0 sets in the permutation space $\mathsf{\Pi }$: a class $X\subseteq \mathsf{\Pi }$ has measure 0 if and only if there a permutation martingale $d$ with $X\subseteq S^{\mathrm{\infty }}[d]$. This permutation martingale characterization allows us to impose computability and complexity constraints in the same way Lutz did for resource-bounded measure in Cantor space [14]. In the following, let $\mathrm{\Delta }$ be a resource bound such as $𝗉$, ${𝗉}_{{}_2}$, $\mathrm{𝗉𝗌𝗉𝖺𝖼𝖾}$, or ${𝗉}_{{}_2}\mathrm{𝗌𝗉𝖺𝖼𝖾}$ (see Section 3.5 for more details).

Betting games [6, 18] are a generalization of martingales that are allowed to bet on strings in an adaptive order rather than the standard order. We analogously introduce permutation betting games as a generalization of both permutation martingales and classical betting games by allowing the betting strategy to adaptively choose the order in which it bets on the permutation’s values. We use these betting games to define resource-bounded permutation betting-game measure.

We also define individually random permutations.

Our main result strengthens the Bennett–Gill permutation separation by proving that $𝖯\ne \mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$ relative to every polynomial-time betting-game random permutation $\pi$. Formally, Theorem 5.1 establishes that

for every $𝗉$-betting-game random permutation $\pi$. In fact, we obtain even stronger separations in terms of bi-immunity [8, 2], a notion formalizing the absence of infinite, easily-decidable subsets (see Section 5 for more details). We show that for a $𝗉$-betting-game random permutation $\pi$, the class ${\mathrm{𝖭𝖫𝖨𝖭}}^{\pi }\cap {\mathrm{𝖼𝗈𝖭𝖫𝖨𝖭}}^{\pi }$ contains languages that are bi-immune to ${\mathrm{𝖣𝖳𝖨𝖬𝖤}}^{\pi }(2^{kn})$ for all $k\ge 1$, where $\mathrm{𝖭𝖫𝖨𝖭}$ denotes nondeterministic linear time. Moreover, relative to a ${𝗉}_{{}_2}$-betting-game random permutation, we derive that ${\mathrm{𝖭𝖯}}^{\pi }\cap {\mathrm{𝖼𝗈𝖭𝖯}}^{\pi }$ contains languages that are bi-immune to ${\mathrm{𝖣𝖳𝖨𝖬𝖤}}^{\pi }(2^{n^k})$ for every $k\ge 1$.

Bennett et al. [3] showed that ${\mathrm{𝖭𝖯}}^{\pi }\cap {\mathrm{𝖼𝗈𝖭𝖯}}^{\pi }⊈{\mathrm{𝖡𝖰𝖳𝖨𝖬𝖤}}^{\pi }(o(2^{n/3}))$ relative to a random permutation $\pi$ with probability 1. We apply our resource-bounded permutation measure framework to improve this to individual space-bounded random oracles. Specifically, we show that relative to a ${𝗉}_{{}_2}\mathrm{𝗌𝗉𝖺𝖼𝖾}$-random permutation $\pi$,

This illustrates the power of our framework for analyzing the interplay between randomness, classical complexity, and quantum complexity.

Tardos [23] proved that if $\mathrm{𝖠𝖬}\cap \mathrm{𝖼𝗈𝖠𝖬}\ne \mathrm{𝖡𝖯𝖯}$, then ${𝖯}^A\ne {\mathrm{𝖭𝖯}}^A\cap {\mathrm{𝖼𝗈𝖭𝖯}}^A$ with probability 1 for a random oracle $A$. This is proved using $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}$ complexity classes. For a relativizable complexity class $𝒞$, its $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}𝒞$ class consists of all languages that are in the class with probability 1 relative to a random oracle: $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}𝒞=\{L\mid \mathrm{𝖯𝗋}[L\in {𝒞}^A]=1\}.$ We have $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}𝖯=\mathrm{𝖡𝖯𝖯}$ [4] and $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}\mathrm{𝖭𝖯}=\mathrm{𝖠𝖬}$ [20]. The condition $\mathrm{𝖠𝖬}\cap \mathrm{𝖼𝗈𝖠𝖬}\ne \mathrm{𝖡𝖯𝖯}$ implies that there exist problems in $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}\mathrm{𝖭𝖯}\cap \mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}\mathrm{𝖼𝗈𝖭𝖯}$ that are not in $\mathrm{𝖠𝖫𝖬𝖮𝖲𝖳}\text{-}𝖯$. Since the intersection of measure 1 classes is measure 1, this implies ${\mathrm{𝖭𝖯}}^A\cap {\mathrm{𝖼𝗈𝖭𝖯}}^A\ne {𝖯}^A$ relative to a random oracle $A$ with probability 1. Recent work of Ghosal et al. [9] shows that if $\mathrm{𝖴𝖯}⊈\mathrm{𝖱𝖯}$, then ${𝖯}^A\ne {\mathrm{𝖭𝖯}}^A\cap {\mathrm{𝖼𝗈𝖭𝖯}}^A$ with probability 1 for a random oracle $A$. In Section 7 we pivot from permutation randomness to classical random oracles and show that resolving the long-standing question “does ${𝖯}^R={\mathrm{𝖭𝖯}}^R\cap {\mathrm{𝖼𝗈𝖭𝖯}}^R$ with probability 1?” is tightly linked to quantitative structure inside $\mathrm{𝖤𝖷𝖯}$. Leveraging the conditional oracle separations of Tardos [23] and of Ghosal et al. [9], we prove that if ${𝖯}^R={\mathrm{𝖭𝖯}}^R\cap {\mathrm{𝖼𝗈𝖭𝖯}}^R$ holds almost surely, then several familiar subclasses of $\mathrm{𝖤𝖷𝖯}$ obey strong 0-1 laws: specifically, either $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$, $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$, (and, in a weaker form, $\mathrm{𝖴𝖯}$ vs. $\mathrm{𝖥𝖾𝗐𝖯}$) each has $𝗉$-measure 0 or else fills all of $\mathrm{𝖤𝖷𝖯}$. Consequently, non-measurability of any one of these classes immediately forces ${𝖯}^R\ne {\mathrm{𝖭𝖯}}^R\cap {\mathrm{𝖼𝗈𝖭𝖯}}^R$ with probability 1. We further show that placing the same oracle separation in ${𝗉}_{{}_2}$ measure would collapse BPP below EXP, thereby framing the random-oracle problem in terms of concrete measure-theoretic thresholds inside exponential time.

This paper is organized as follows: Section 2 contains preliminaries. Section 3 develops permutation martingales, resource-bounded permutation measure, and random permutations. Elementary properties of $𝗉$-random permutations are presented in Section 4. In Section 5, we prove our main results on random permutations for $𝖯$ vs. $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$. Section 6 contains our results on $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$ versus quantum computation relative to a random permutation. In Section 7 we present our results on random oracles and 0-1 laws. We conclude in Section 8 with some open questions.

Resource-bounded measure is typically defined in the Cantor Space $𝖢={\{0,1\}}^{\mathrm{\infty }}=2^{\mathbb{N}}$ of all infinite binary sequences. For measure in $𝖢$, we use the open balls or cylinders ${𝖢}_w=w\cdot 𝖢$ that have measure $\mu ({𝖢}_w)=2^{-|w|}$ for each $w\in {\mathrm{\Sigma }}^{\ast }$. Let $𝒞$ be the $\sigma$-algebra generated by $\{{𝖢}_w\mid w\in {\{0,1\}}^{\ast }\}$. Resource-bounded measure and algorithmic randomness typically work in the probability space $(𝖢,𝒞,\mu )$.

We only consider permutations in $\mathsf{\Pi }$, the set of permutations on ${\{0,1\}}^{\ast }$ that preserve string lengths. Given a permutation $\pi \in \mathsf{\Pi }$, we denote by ${\pi }_n$ the permutation $\pi$ restricted to ${\{0,1\}}^n$ i.e., ${\pi }_n$ is a permutation on ${\{0,1\}}^n$. Similarly, ${\mathsf{\Pi }}_n$ denotes the set of permutations in $\mathsf{\Pi }$ restricted to ${\{0,1\}}^n$. Bennett and Gill [4] considered random permutations by placing the uniform measure on each ${\mathsf{\Pi }}_n$ and taking the product measure to get a measure on $\mathsf{\Pi }$. We now define this measure space more formally so we may place martingales on it.

Standard resource-bounded measure identifies a language $A\subseteq {\{0,1\}}^{\ast }$ with its infinite binary characteristic sequence ${\chi }_A\in 𝖢$. For permutations, we analogously use the value sequence consisting of all function values.

We identify a permutation $f\in \mathsf{\Pi }$ with its value sequence ${\nu }_f$. Initial segments of permutations are called prefix partial permutations.

We write each $g\in \mathrm{𝖯𝖯}\mathsf{\Pi }$ as a list $g=[g(s_0),\mathrm{\dots },g(s_{N-1})]$. The length of $g$ is $N$, the number of function values assigned, and is denoted $|g|$. We use $[]$ to denote the empty list, the list of length 0. We write $f\upharpoonright N$ for the length $N$ prefix partial permutation of $f\in \mathsf{\Pi }$.

For measure in $\mathsf{\Pi }$, we are taking the uniform distribution on the set of all ${\mathsf{\Pi }}_n$ of length-preserving permutations for all $n$. Our basic open sets are $\{⟦g⟧\mid g\in \mathrm{𝖯𝖯}\mathsf{\Pi }\}$. Suppose $g\in \mathrm{𝖯𝖯}\mathsf{\Pi }$ has $|g|=2^n-1$ for some $n\ge 0$. Then, following Bennett and Gill [4], the measure

is easy to define because the distribution is uniform over the $(2^k)!$ permutations at each length. If , let $m=|g|-2^n+1$ and then

where $P(n,k)=\frac{n!}{(n-k)!}$ denotes the number of $k$-permutations on $n$ elements. For convenience, we commonly write $\mu (g)=\mu (⟦g⟧).$

Let ${ℱ}_{\mathsf{\Pi }}=\sigma (\mathrm{𝖯𝖯}\mathsf{\Pi })$ be the $\sigma$-algebra generated by the collection of all $⟦g⟧$ where $g\in \mathrm{𝖯𝖯}\mathsf{\Pi }.$ By Carathéodory’s extension theorem, $\mu$ extends uniquely to ${ℱ}_{\mathsf{\Pi }}$, yielding the probability space $(\mathsf{\Pi },{ℱ}_{\mathsf{\Pi }},\mu ).$ We will work in this probability space. Because $\mu$ is outer regular, we have the typical open cover characterization of measure zero:

In resource-bounded measure in Cantor Space, a martingale is a function $d:{\mathrm{\Sigma }}^{\ast }\to [0,\mathrm{\infty })$ such that for all $w\in {\mathrm{\Sigma }}^{\ast }$, we have the following averaging condition:

A martingale in Cantor space may be viewed as betting on the membership of strings in a language. The standard enumeration of ${\{0,1\}}^{\ast }$ is $s_0=\lambda ,s_1=0,s_2=1,s_3=00,s_4=01,\mathrm{\dots }$. In the $i^{\mathrm{th}}$ stage of the game, the martingale has seen the membership of the first $i$ strings and bets on the membership of $s_i$ in the language. The martingale’s value is updated based on the outcome of the bet. For further background on resource-bounded measure, we refer to [14, 15, 1, 6, 10].

A permutation martingale operates similarly, but instead of betting on the membership of a string in a language it bets on the next function value of the permutation. Instead of seeing the characteristic string of a language, a permutation martingale sees a prefix partial permutation, which is a list of permutation function values $g=[g(s_0),\mathrm{\dots },g(s_{i-1})]$ satisfying $|g(s_i)|=|s_i|$ for all $i$. The permutation martingale will bet on the next function value $g(s_i)$. The current betting length is the length of the next string $s_{|g|}$ in the standard enumeration: $l(g)=|s_{|g|}|.$ The set of free strings available for the next function value is

For example, $\mathrm{𝖿𝗋𝖾𝖾}([\lambda ])=\{0,1\}$, $\mathrm{𝖿𝗋𝖾𝖾}([\lambda ,1,0,11])=\{00,01,10\}$, and $\mathrm{𝖿𝗋𝖾𝖾}([\lambda ,1,0,11,00,01])=\{10\}$.

We now introduce our main conceptual contribution, permutation martingales.

Success is defined for permutation martingales analogously to success for classical martingales.

We establish the analogue of Ville’s theorem [25] for measure in $\mathsf{\Pi }$ and permutation martingales:

We construct a permutation martingale $d$ that succeeds on any length-preserving permutation whose restriction to length $n$ is a cycle permutation for all but finitely many $n$. We partition the initial capital into infinitely many shares $a_i=1/i^2$. For each $i$, the share $a_i$ is used to bet on the event that, for all $n\ge i$, the length-$n$ restriction of the permutation is a cycle permutation.

The betting strategy is simple: when moving from length $n-1$ to $n$, the martingale wagers all relevant capital on the image of the $n$-bit string $1^{n-1}0$. In the final step of forming a cycle of length $2^n$, there are exactly two choices for the image of $1^{n-1}0$. One choice yields a cycle of length $2^n$; the other does not. Since it is a binary choice, the martingale places its entire stake $a_i$ (for all $i\le n$) on the cycle outcome, thereby doubling its capital whenever the cycle is formed.

Hence, on any permutation whose restriction to length $n$ is a cycle permutation for all but finitely many $n$, infinitely many of these bets succeed. Consequently, each of those corresponding shares $a_i$ grows without bound, and so the overall martingale $d$ succeeds on all such permutations.

Hitchcock and Lutz [11] showed how the martingales used in computational complexity are a special case of martingales used in probability theory. We explain how this extends to permutation martingales. Given a martingale $d:{\{0,1\}}^{\ast }\to [0,\mathrm{\infty })$, Hitchcock and Lutz define the random variable ${\xi }_{d,n}:𝖢\to [0,\mathrm{\infty })$ by ${\xi }_{d,n}(S)=d(S\upharpoonright n)$ for each $n\ge 0$. Let ${ℳ}_n=\sigma (\{{𝖢}_w\mid w\in {\{0,1\}}^n\})$ be the $\sigma$-algebra generated by the cylinders of length $n$. Then the sequence $({\xi }_{d,n}\mid n\ge 0)$ is a martingale in the probability theory sense with respect to the filtration $({ℳ}_n\mid n\ge 0)$: for all $n\ge 0$, $E[{\xi }_{d,n+1}\mid {ℳ}_n]={\xi }_{d,n}.$

Similarly, given a permutation martingale $d:\mathrm{𝖯𝖯}\mathsf{\Pi }\to [0,\mathrm{\infty })$, for each $N$ we can define the random variable $X_{d,N}:\mathsf{\Pi }\to [0,\mathrm{\infty })$ by $X_{d,N}(f)=d(f\upharpoonright N)$ for each $N\ge 0$. Let

be the $\sigma$-algebra generated by the cylinders in $\mathrm{𝖯𝖯}\mathsf{\Pi }$ of length $N$. Then $(X_{d,N}\mid N\ge 0)$ is a martingale in the probability theory sense with respect to the filtration $({𝒢}_N\mid N\ge 0)$: for all $N\ge 0$, $E[X_{d,N+1}\mid {𝒢}_N]=X_{d,N}.$

We follow the standard notion of computability for real-valued functions [14] to define resource-bounded permutation martingales.

We are now ready to define resource-bounded permutation measure.

Equivalently, $\pi$ is $\mathrm{\Delta }$-random if no $\mathrm{\Delta }$-martingale succeeds on $\pi$.

Originated in the field of algorithmic information theory, betting games are a generalization of martingales [19, 18], which were introduced to computational complexity by Buhrman et al. [6]. Similar to martingales, betting games can be thought of as strategies for betting on a binary sequence, except that with betting games we have the additional capability of selecting which position in a sequence to bet on next. In other words, a betting game is permitted to select strings in a nonmonotone order, with the important restriction that it may not bet on the same string more than once (see Buhrman et al. [6] for more details).

A permutation betting game is a generalization of a permutation martingale, implemented by an oracle Turing machine, where it is allowed to select strings in nonmonotone order. Prefixes of permutation betting games can be represented as ordered partial permutations defined below.

For a permutation betting game, the averaging condition takes into consideration the length of the next string to be queried as follows. Let $w\in \mathrm{𝖮𝖯}\mathsf{\Pi }$ be the list of queried strings paired with their images, and $a\in {\{0,1\}}^n$ be the next string the betting game will query. Define free$(w,n)$ to be the set of length-$n$ strings that are available for the next function value, i.e., length-$n$ strings that are not the function value of any of the queried strings. Then the following averaging condition over free strings of length $n$ must hold for the permutation betting game $d:\mathrm{𝖮𝖯}\mathsf{\Pi }\to [0,\mathrm{\infty })$

where $w[a,b]$ is the list $w$ appended with the pair $(a,b)$.

We define betting game measure 0 and betting game randomness analogously.

Lutz’s Measure Conservation Theorem implies that resource-bounded measure gives nontrivial notions of measure within exponential-time complexity classes: ${\mu }_{𝗉}(𝖤)\ne 0$ and ${\mu }_{{𝗉}_{{}_2}}(\mathrm{𝖤𝖷𝖯})\ne 0$. Let $\mathrm{𝖯𝖾𝗋𝗆𝖤}$ be the class of length-preserving permutations that can be computed in $2^{O(n)}$ time and $\mathrm{𝖯𝖾𝗋𝗆𝖤𝖷𝖯}$ be the class of length-preserving permutations that can be computed in $2^{n^{O(1)}}$ time. We show that our notions of permutation measure have conservation theorems within these classes of exponential-time computable permutations.

The following theorem follows from Lemma 3.14.

Proving similar results for betting games turns out to be more challenging, given that they are allowed to bet on strings in an adaptive order. To address this, we define the following class of honest betting games.

We use this definition in the following Lemma:

Since $\mathrm{𝗉𝗌𝗉𝖺𝖼𝖾}$-permutation martingales can simulate $O(n)$-honest $𝗉$-betting-games, and ${𝗉}_{{}_2}\mathrm{𝗌𝗉𝖺𝖼𝖾}$-permutation martingales can simulate $O(n^k)$-honest ${𝗉}_{{}_2}$-betting-games, we have the following:

The proof uses a simple averaging argument: we partition the set of length-$n$ strings into $2^n/n^{\lg n}$ subintervals, each of size $n^{\lg n}$. By the noticeably-polynomial-time property of the permutations in $X$, at least one subinterval contains superpolynomially many strings whose images are computable. The martingale then identifies a sufficiently small subset of these strings and makes correct predictions often enough to succeed.

Similarly, we can show that random permutations are hard to invert on a noticeable subset infinitely often. The main difference is that we search for TMs inverting the permutation rather than TMs that compute the permutation.

Bennett and Gill used random permutations, rather than random languages, to separate $𝖯$ from $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$. It is still unknown whether random oracles separate $𝖯$ from $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$. In this section, we examine how random permutations yield random languages. We show that a $𝗉$-random permutation can be used to generate a $𝗉$-random language. All of the results in this section are stated for $𝗉$-randomness. They also hold for ${𝗉}_{{}_2}$-randomness.

Given a permutation $\pi \in \mathsf{\Pi }$, we define the language

For a set of permutations $X\subseteq \mathsf{\Pi }$, we define the set of languages

We now extend the previous lemma to honest $𝗉$-permutation betting games. By Lemma 3.17, honest $𝗉$-permutation betting games do not cover $\mathrm{𝖯𝖾𝗋𝗆𝖤}$ and honest ${𝗉}_2$-permutation betting games do not cover $\mathrm{𝖯𝖾𝗋𝗆𝖤𝖷𝖯}$.