Metraipolis › archive › dc_012aa8925514
TFNP in the Random Oracle Model — arXiv:2611.05308
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05308
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T13:00:28.559Z
- SHA-256 of the archived text
162f145791e4ec8e3604c4440876fa472551cb40fd252a11994e7b73a2958922- Stable URL of this page
https://metraipolis.com/documento/dc_012aa8925514
How to cite
TFNP in the Random Oracle Model — arXiv:2611.05308 — arXiv (en), https://arxiv.org/abs/2611.05308 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_012aa8925514 (Metraipolis archive dc_012aa8925514, sha256 162f145791e4ec8e3604c4440876fa472551cb40fd252a11994e7b73a2958922)
BibTeX
@misc{dc012aa8925514,
title = {TFNP in the Random Oracle Model — arXiv:2611.05308},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05308},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_012aa8925514; sha256 162f145791e4ec8e3604c4440876fa472551cb40fd252a11994e7b73a2958922},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05308. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We determine which major $\TFNP$ classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of $\TFNP$ from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard $\TFNP$ subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: $\PPAD$, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of $\EoPL = \PPAD \cap \PLS$. In contrast, we show that $\UEoPL$ can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between $\EoPL$ and $\UEoPL$. This resolves the black-box hardness landscape of all major $\TFNP$ classes in Romantica. Finally, we initiate the study of separations between $\TFNP$ subclasses in Romantica: $\PWPP$ and $\PPA$ do not reduce to $\PLS$ under \emph{public-coin} reductions.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.05308 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:35:32.303Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).