Powered by OpenAIRE graph
Found an issue? Give us feedback
ZENODOarrow_drop_down
ZENODO
Preprint . 2026
License: CC BY
Data sources: Datacite
ZENODO
Preprint . 2026
License: CC BY
Data sources: Datacite
versions View all 2 versions
addClaim

P vs NP as Observer-Dependent Computational Hardness: A Reinterpretation through Dynamic Gate Numbers

Authors: Yang, Jihoon;

P vs NP as Observer-Dependent Computational Hardness: A Reinterpretation through Dynamic Gate Numbers

Abstract

P vs NP as Observer-Dependent Computational Hardness:A Reinterpretation through Dynamic Gate Numbers This paper offers a reinterpretation of the P vs NP problem through the framework of Dynamic Gate Numbers, treating computational hardness as a relational and state-dependent quantity rather than an intrinsic, observer-independent property of problem instances. The work does not claim to resolve P vs NP in its classical formulation, nor does it challenge established results in complexity theory such as NP-completeness or time hierarchy theorems. Instead, it examines why the P vs NP question has remained persistent by relaxing three implicit assumptions of classical complexity theory: fixed computational models, observer-independent hardness, and memoryless computation. Within the Dynamic Gate Numbers framework, computational cost is modeled as a trajectory-valued quantity that depends on an agent’s internal state and the set of admissible transitions (gates) available to that agent. Hardness emerges from the interaction between problem structure and gate-constrained agents, rather than from problem instances alone. The paper establishes three main results: Impossibility of universal hardness measures — when agents learn and adapt, no observer-independent scalar function can faithfully represent computational difficulty. Gate-dependent complexity — the same problem instance may exhibit P-like behavior for one agent and NP-like behavior for another, without any modification to the problem itself. Persistence of NP-hardness — apparent NP-hardness persists when an agent’s gate capacity is structurally bounded, regardless of learning, indicating that hardness endurance is a capacity phenomenon rather than an intrinsic property of problems. Classical complexity theory is recovered as a special case of this framework, corresponding to fixed gates and state-independent cost functions. The reinterpretation preserves all standard definitions of P and NP while situating them within a broader class of adaptive computational systems. This work is theoretical and interpretive. It introduces no new algorithms, simulations, or empirical claims. Its contribution lies in clarifying the structural conditions under which computational hardness appears stable, relative, or persistent, and in providing a mathematical language for discussing learning and adaptation within complexity theory.

  • 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
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!