Metraipolis › archive › dc_f0ffa71cf2f9

Predictor-Impossibility Theorem and Applications — arXiv:2608.05613

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.05613
License (as archived)
CC0-1.0
Archived
2026-10-31T10:51:06.861Z
SHA-256 of the archived text
d21f5adfa3b467669a8f11185e4981380607c4f5832904f9707c57118fe33393
Stable URL of this page
https://metraipolis.com/documento/dc_f0ffa71cf2f9

How to cite

Predictor-Impossibility Theorem and Applications — arXiv:2608.05613 — arXiv (en), https://arxiv.org/abs/2608.05613 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f0ffa71cf2f9 (Metraipolis archive dc_f0ffa71cf2f9, sha256 d21f5adfa3b467669a8f11185e4981380607c4f5832904f9707c57118fe33393)
BibTeX
@misc{dcf0ffa71cf2f9,
  title = {Predictor-Impossibility Theorem and Applications — arXiv:2608.05613},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.05613},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f0ffa71cf2f9; sha256 d21f5adfa3b467669a8f11185e4981380607c4f5832904f9707c57118fe33393},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05613. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We introduce a hierarchy consisting of stage machines, stage domains, and stage languages generated by semantic operators. The central result is a Predictor Impossibility Theorem (PITT), which shows that no effective predictor family can uniformly determine all stage languages of our hierarchy. The proof makes use of a pseudo-complement construction to obtain a language that yields a contradiction with every language in P. We then define an aggregate language MIS and establish a formal Slice Theorem connecting aggregate inputs to individual stage languages. This provides a rigorous Bridge Theorem from polynomial-time decidability of MIS to the existence of an effective predictor family. By utilizing succinct representations, the aggregate language is shown to be undecidable in deterministic polynomial time. Under the aggregate growth condition defining valid aggregate objects, MIS is shown to belong to NP. Combining these two results yields our main theorem: MIS in NP setminus P. The paper is organized so that PITT stands independently as a theoretic result, while the complexity-theoretic consequences are derived from the aggregate-language framework. The method does not relativize, algebrize, or naturalize.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-07 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.05613 — 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-10-31T10:38:22.104Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).