Information asymmetry and incorrect classification of classes P and NP
This article reveals a fundamental epistemological asymmetry in the current formulation of the problem of comparing P and NP. It demonstrates that the widespread assumption of "polynomial-time verifiability" implicitly requires the pre-entry of an existing solution key into the system, which effectively reduces the task to non-algorithmic data replication. In the absence of an explicitly provided key, the computational complexity of the verification process is inherently the same as the complexity of the brute force search itself. Consequently, it is shown that the traditional division between classes P and NP is more an artifact of the asymmetric distribution of information than an inherent property of computational problems. By rethinking the problem using unified key data sectors, we resolve this paradox and show that with adjusted symmetric classification, the obvious discrepancy between resolution and validation disappears.
Authors
- Vadim Kan
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-11
- DOI
- https://doi.org/10.5281/zenodo.22714416
- Primary Topic
- Adversarial Robustness in Machine Learning
- Type
- preprint