Random Permutations in Computational Complexity A preliminary version of this paper appeared the Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) [ 16 ] .

John M. Hitchcock, Adewale Sekoni, Hadi Shafei · 2025

Read Random Permutations in Computational Complexity A preliminary version of this paper appeared the Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) [ 16 ] . by John M. Hitchcock, Adewale Sekoni, Hadi Shafei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08786.txt.

Description

John Hitchcock, Adewale Sekoni, and Hadi Shafei revisit a classic question in computational complexity: how do the classes P and NP behave when algorithms can consult a random permutation as an oracle? Bennett and Gill showed decades ago that a random permutation separates P from the intersection of NP and coNP with probability one.

The new work strengthens that almost-everywhere statement to individually random permutations. Permutation martingales and betting games define what randomness means for a single permutation under resource bounds. The main theorem then separates the classes for every polynomial-time betting-game random permutation. A quantum separation from the nineteen nineties is also strengthened. The authors further show random oracles can be built from random permutations, while the reverse direction stays open.

Catalog record

CREATORJohn M. Hitchcock, Adewale Sekoni, Hadi Shafei
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08786

Browse the full library · About the Tower of Babel