Abstract
Classical results of Bennett and Gill (1981) show that with probability 1, PA ̸= NPA relative to a random oracle A, and with probability 1, Pπ ≠ NPπ ∩ coNPπ relative to a random permutation π. Whether PA = NPA ∩ coNPA 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π ̸= NPπ ∩ coNPπ for every polynomial-time betting-game random permutation π. 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π ∩coNPπ ̸⊆ BQPπ for every polynomialspace random permutation π.
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 ∩ coNP is not a measurable subset of EXP, then PA ̸= NPA ∩ coNPA 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 resourcebounded 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.
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π ̸= NPπ ∩ coNPπ for every polynomial-time betting-game random permutation π. 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π ∩coNPπ ̸⊆ BQPπ for every polynomialspace random permutation π.
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 ∩ coNP is not a measurable subset of EXP, then PA ̸= NPA ∩ coNPA 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 resourcebounded 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.
| Original language | English |
|---|---|
| Title of host publication | 50th International Symposium on Mathematical Foundations of Computer Science |
| Subtitle of host publication | (MFCS 2025) |
| Editors | Paweł Gawrychowski, Filip Mazowiecki, Michał Skrzypczak |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Number of pages | 17 |
| ISBN (Electronic) | 9783959773881 |
| DOIs | |
| Publication status | Published - 20 Aug 2025 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 345 |
| ISSN (Print) | 1868-8969 |