Classical results of Bennett and Gill (1981) show that with probability 1, $P^A \neq NP^A$ relative to a random oracle $A$, and with probability 1, $P^\pi \neq NP^\pi \cap coNP^\pi$ relative to a random permutation $Pi$. Whether $P^A = NP^A \cap coNP^A$ holds relative to a random oracle $A$ remains open. While the random oracle separation has been extended to specific individually random oracles--such as Martin-Löf random or resource-bounded random oracles--no analogous result is known for individually random permutations.
We introduce a new resource-bounded measure framework for analyzing individually random permutations. We define permutation martingales and permutation betting games that characterize measure-zero sets in the space of permutations, enabling formal definitions of polynomial-time random permutations, polynomial-time betting-game random permutations, and polynomial-space random permutations.
Our main result shows that $P^\pi \neq NP^\pi \cap coNP^\pi$ for every polynomial-time betting-game random permutation $Pi$. This is the first separation result relative to individually random permutations, rather than an almost-everywhere separation. We also strengthen a quantum separation of Bennett, Bernstein, Brassard, and Vazirani (1997) by showing that $NP^\pi \cap coNP^\pi \not\subseteq BQP^\pi$ for every polynomial-space random permutation $Pi$.
We investigate the relationship between random permutations and random oracles. We prove that random oracles are polynomial-time reducible from random permutations. The converse--whether every random permutation is reducible from a random oracle--remains open. We show that if $NP \cap coNP$ is not a measurable subset of $EXP$, then $P^A \neq NP^A \cap coNP^A$ holds with probability 1 relative to a random oracle $A$. Conversely, establishing this random oracle separation with time-bounded measure would imply $BPP$ is a measure 0 subset of $EXP$.
Our framework builds a foundation for studying permutation-based complexity using resource-bounded measure, in direct analogy to classical work on random oracles. It raises natural questions about the power and limitations of random permutations, their relationship to random oracles, and whether individual randomness can yield new class separations.
