Metraipolis › archive › dc_c6ef54585291
On Positive Computation — arXiv:2611.09622
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.09622
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:47:25.750Z
- SHA-256 of the archived text
3be324ec43d10782b77728d0223a91ad9101853ff534257184a3b219afc7b717- Stable URL of this page
https://metraipolis.com/documento/dc_c6ef54585291
How to cite
On Positive Computation — arXiv:2611.09622 — arXiv (en), https://arxiv.org/abs/2611.09622 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c6ef54585291 (Metraipolis archive dc_c6ef54585291, sha256 3be324ec43d10782b77728d0223a91ad9101853ff534257184a3b219afc7b717)
BibTeX
@misc{dcc6ef54585291,
title = {On Positive Computation — arXiv:2611.09622},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.09622},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c6ef54585291; sha256 3be324ec43d10782b77728d0223a91ad9101853ff534257184a3b219afc7b717},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09622. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce new notions of reducibility for monotone classes and show that a monotone version of Circuit Satisfiability and the Hamiltonian Cycle Problem are complete for $mNP$, even under positive reductions (which are not the same as monotone reductions). If this holds for all (monotone) $mNP$-complete problems - that they are also so complete for $mNP$ -, then $P\neq NP$. We introduce positive models of relativized computation and show that the separation $posP\subsetneq mNP$ does not relativize, even when oracles are restricted to monotone sets. Yet, there is a (weak) diagonalization proof that $posP\subsetneq mNP$. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC) ; Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2611.09622 — 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-09T22:40:44.874Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).