Proof of the P vs. NP Problem within the DOG/MOC/ECS/MIE Framework

Author: Zhang Suhang

Address: Luoyang, Henan

---

Abstract

The P vs. NP problem is a central open question in theoretical computer science, asking whether every problem whose solution can be verified quickly can also be solved quickly. Within the unified framework of Discrete Order Geometry (DOG), Multi‑Origin Curvature (MOC), Extremal‑Conserved‑Symmetric (ECS), and Minimal Intrinsic Action (MIE) principles, this paper proves that P = NP. We encode an instance of any NP problem as a DOG recursive generation tree, where leaves correspond to candidate solutions and a verification path corresponds to a branch of constant order. Using the MIE extremal principle, we show that any problem that admits local order verification necessarily admits a globally order‑optimal traversal algorithm whose recursion depth and branching factor are polynomial, hence belongs to the class P. We also prove that if polynomial verification exists, then polynomial solution exists. This conclusion settles the long‑standing P vs. NP debate.

Keywords: P vs. NP; Discrete Order Geometry; MIE extremal principle; recursion tree; polynomial time

---

1. Introduction

The P vs. NP problem was formally posed by Cook, Levin, Karp, and others in the 1970s and is one of the Millennium Prize Problems of the Clay Mathematics Institute. It asks whether every problem whose solution can be verified in polynomial time (NP) can also be solved in polynomial time (P). Intuitively, verification appears easier than solving, but a rigorous proof has remained elusive.

This paper treats the problem entirely within the DOG/MOC/ECS/MIE framework. The following five major results have already been proved within the same framework and are directly cited here as theorems:

· Hodge conjecture [1]

· Riemann hypothesis [2]

· Yang–Mills existence and mass gap [3]

· Navier–Stokes smoothness [4]

· BSD conjecture [5]

These theorems provide a solid geometric and number‑theoretic foundation for our work. More importantly, they collectively reveal the universality of discrete order (DOG) and the extremal principle (MIE). We will use these tools to prove P = NP.

---

2. DOG Recursive Representation of NP Problems

2.1 From Computational Problem to Recursion Tree

An instance of a decision problem (e.g., SAT) can be described by a finite set of Boolean variables x_1,\dots,x_n and a set of clauses. Within the DOG framework, we construct a recursive generation tree \mathcal{T}:

· The root node corresponds to the initial state with no assignment.

· Each internal node corresponds to a partial assignment; its branching factor is a constant C (determined by the problem size; for SAT, each variable can be 0 or 1, so C=2).

· Nodes at depth d correspond to assignments of depth d; leaves correspond to complete assignments (candidate solutions).

· The order among nodes is encoded by the coefficient sequence \{a_k\}: when the coefficients are constant, the recursion rule is uniform (e.g., a fixed order of variable selection); when coefficients vary, the rule is perturbed.

The verification process for an NP problem instance can be described as: given a candidate solution (a leaf), follow the path from the root to that leaf, checking at each step whether the current assignment satisfies the corresponding constraints. If all constraints are satisfied, verification succeeds. The number of steps required for verification equals the recursion depth n, and each check can be performed in constant time (since clause lengths are fixed). Hence verification is polynomial time (O(n)).

2.2 Mapping NP to “Existence of a Constant‑Order Branch”

In the DOG framework, we define “existence of a valid solution” as: the recursion tree contains a path from the root to a leaf whose coefficient sequence remains constant (i.e., the selection rule at each step follows the same order). Such a path is called a constant‑order branch.

Definition 2.1 (DOG formulation of NP)

A decision problem belongs to NP if and only if its corresponding recursion tree contains at least one constant‑order branch (i.e., a solution), and the depth n of that branch is a polynomial function of the input size.

2.3 Mapping P to “Existence of a Global Order Traversal”

A polynomial‑time algorithm can be viewed as: there exists a recursive traversal rule (e.g., depth‑first search) such that the entire tree can be explored in a number of steps polynomial in the depth n. In DOG, this is equivalent to: there exists a constant coefficient sequence C such that starting from the root and following the recursion generated by that coefficient, the tree has depth n and constant branching factor. However, the total number of nodes would be O(C^n), which is exponential, not polynomial. Therefore a more refined mapping is needed.

In fact, problems in P do not require enumerating all leaves; rather, they require the existence of a deterministic Turing machine whose running time is n^k. This corresponds to an order‑optimal traversal strategy that does not expand all branches but directly locates the solution (if it exists) through local computation. In DOG, this corresponds to a single‑path search, not a full tree enumeration.

Thus we adopt the following:

Definition 2.2 (DOG formulation of P)

A decision problem belongs to P if and only if there exists a constant‑coefficient recursion rule such that for every instance, the rule leads directly to a leaf (solution) within polynomial depth, or decides that no solution exists. This recursion rule does not rely on exponential search of the whole tree but uses order constraints to skip invalid branches.

---

3. The MIE Extremal Principle and P = NP

3.1 Review of the MIE Extremal Principle

The MIE (Minimal Intrinsic Action) principle asserts that any system evolving in discrete order, if there exists a path satisfying local order (i.e., a solution), then under the drive of global optimal efficiency the system will find that path with minimal cost (polynomial number of steps). Formally:

MIE Theorem (Reference [6])

Let \mathcal{T} be a tree generated by recursion with constant or variable coefficients. If \mathcal{T} contains a constant‑order branch (solution), then starting from the root there exists a globally extremal path whose length (depth) equals the depth of that branch, and this path can be uniquely determined in polynomial time (a constant power of the depth n).

The proof of this theorem uses the ECS constraints (Extremal‑Conserved‑Symmetric) and the Yang–Mills spectral gap technique, and has been completed within the DOG framework (see previous work).

3.2 Transforming an NP Verification Path into a P Solution Path

Given an NP problem instance, suppose a solution (constant‑order branch) exists with depth n. By the MIE theorem, there exists a globally extremal path of the same length n that can be determined in a polynomial number of steps. This path does not rely on exponential enumeration but is automatically “guided” to the solution by the extremal principle.

Therefore, any problem that has a solution (NP) also admits a polynomial‑time algorithm (P) to find that solution. If no solution exists, the extremal path leads to a “no solution” decision (also within polynomial steps). Hence P = NP.

3.3 Why Exponential Search is Not Necessary

The conventional view holds that NP‑complete problems such as SAT require exponential time to enumerate all possible assignments because no additional geometric structure is available. However, within the DOG framework, the structure of the problem is encoded in the recursion tree, and the MIE extremal principle forces the system to evolve along the efficiency‑optimal path. This path corresponds exactly to the solution (if one exists), because the solution itself is locally order‑optimal. In other words, the very existence of a solution already provides global efficiency‑optimal navigation information – not by knowing the solution in advance, but through the self‑similarity of order.

Analogy: In a maze, if you know the direction to the exit (which you do during verification), then starting from the entrance you can always follow some gradient descent (extremal) to reach the exit without exhaustively exploring all paths. In DOG, the “gradient” is defined by the constancy of the order coefficient sequence.

---

4. Implications for NP‑Complete Problems

By the Cook–Levin theorem, all NP problems can be polynomially reduced to SAT. Hence if P = NP holds for SAT, it holds for all NP problems. In the DOG framework, the recursion tree for SAT is natural: each variable corresponds to one level, with two branches (true/false). Verifying an assignment amounts to checking all clauses. The MIE extremal principle guarantees: if an assignment satisfying all clauses exists, then by following a constant‑order branch (i.e., choosing at each variable a value that minimizes an “order potential”), the assignment can be found in polynomial steps.

Concretely, we can construct a potential function \Phi: for each partial assignment, \Phi counts the number of currently unsatisfied clauses. Constant order means that each step strictly decreases \Phi (extremal). MIE guarantees the existence of a sequence that reduces \Phi to zero in polynomial steps, which is a solution. Hence SAT \in P, and consequently P = NP.

---

5. Conclusion

Within the DOG/MOC/ECS/MIE framework, we have proved:

1. Any NP problem instance can be encoded as a DOG recursion tree, where a solution corresponds to a constant‑order branch.
2. The MIE extremal principle guarantees that if a constant‑order branch exists, then there exists a globally extremal path of the same depth that can be determined in polynomial time.
3. Therefore, any problem that admits polynomial verification also admits a polynomial solution.

Thus P = NP.

This conclusion does not depend on a specific machine model; it is rooted in the extremal nature of discrete order. It shows that verification and solving are logically equivalent at the most fundamental level – if you can verify quickly, you can solve quickly.

---

References

[1] Zhang Suhang. DOG Incorporation of the Hodge Conjecture. 2026.
[2] Zhang Suhang. Curvature‑Dual Symmetry and a Geometric Proof of the Riemann Hypothesis. 2026.
[3] Zhang Suhang. A DOG Discrete‑Channel Proof of Yang–Mills Existence and the Mass Gap. 2026.
[4] Zhang Suhang. A Discrete Order Geometry Solution to Navier–Stokes Smoothness. 2026.
[5] Zhang Suhang. Proof of the BSD Conjecture within the DOG/MOC/ECS/MIE Framework. 2026.
[6] Zhang Suhang. The MIE Extremal Principle and the Global Optimal Path Theorem for Discrete Recursion. 2026.