Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2511.08786 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917075411271680 |
|---|---|
| author | Hitchcock, John M. Sekoni, Adewale Shafei, Hadi |
| author_facet | Hitchcock, John M. Sekoni, Adewale Shafei, Hadi |
| contents | 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^π\neq NP^π\cap coNP^π$ relative to a random permutation $π$. 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 resource-bounded random permutations.
Our main result shows that $P^π\neq NP^π\cap 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^π\cap coNP^π\not\subseteq BQP^π$ for every polynomial-space 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 \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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08786 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Random Permutations in Computational Complexity Hitchcock, John M. Sekoni, Adewale Shafei, Hadi Computational Complexity 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^π\neq NP^π\cap coNP^π$ relative to a random permutation $π$. 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 resource-bounded random permutations. Our main result shows that $P^π\neq NP^π\cap 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^π\cap coNP^π\not\subseteq BQP^π$ for every polynomial-space 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 \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$. |
| title | Random Permutations in Computational Complexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.08786 |