Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Other ORP type . 2025
License: CC BY
Data sources: ZENODO
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Other ORP type . 2025
License: CC BY
Data sources: ZENODO
ZENODO
Other ORP type . 2025
License: CC BY
Data sources: Datacite
ZENODO
Other ORP type . 2025
License: CC BY
Data sources: Datacite
ZENODO
Other ORP type . 2025
License: CC BY
Data sources: Datacite
ZENODO
Other ORP type . 2025
License: CC BY
Data sources: Datacite
versions View all 4 versions
addClaim

"Exposure Time and Exploration Preservation A Structural Perspective on the P versus NP Problem"

RP No.15
Authors: KEI, SHIRAISHI;

"Exposure Time and Exploration Preservation A Structural Perspective on the P versus NP Problem"

Abstract

【Description】This research note reinterprets the P versus NP problem through the lens of temporal structure rather than computational speed. By focusing on when contradictions become observable during exploration, the paper introduces exposure time as a unifying concept linking SAT, NP-completeness, polynomial-time reductions, and the limits of heuristic and AI-driven search. The work does not claim a proof of P ≠ NP. Instead, it provides a structural explanation for why exploration persists across representations and algorithmic paradigms. The proposed framework positions P versus NP as a boundary condition on how information, choice, and time interact in combinatorial systems. 【Abstract】The P versus NP problem is traditionally framed as a comparison between the efficiency of solution discovery and verification. This paper proposes a structural reinterpretation based on the temporal behavior of contradiction emergence during exploration. We introduce the notion of exposure time: the point at which a partial assignment becomes provably non-extendable. While problems such as 2-SAT allow exposure time to be advanced to the moment of local choice, NP-complete problems like 3-SAT exhibit delayed exposure, where contradictions emerge only after combinations of choices align. Through minimal structural examples and a reinterpretation of polynomial-time reductions as exposure-time preserving mappings, we argue that NP-completeness reflects robustness of delayed contradiction exposure under representational change. This leads to an exploration preservation principle: when the meaning of choices is generated through combination rather than isolation, exploration cannot be eliminated in principle. We further discuss implications for heuristic search, learning-based systems, and AGI, suggesting that while exposure time may be partially advanced, delayed exposure remains structurally unavoidable. 【Keywords】P versus NPNP-completenessSATreductionsexplorationexposure timestructural complexityAGI

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average