Introduction

Classical complexity theory defines \(P\) as the class of languages decidable in polynomial time by a deterministic Turing machine and \(NP\) as the class decidable in polynomial time by a nondeterministic Turing machine. The open question is whether \(P = NP\).

Pattern Field Theory and the Allen Orbital Lattice introduce an additional structural constraint: computation must maintain phase coherence across active states. In the Coherence-Constrained Computation Theory (CCCT) framework [1], each step of a computation must satisfy a Phase Alignment Lock (PAL) inequality on the AOL. This yields coherence-constrained classes \(\mathrm{PAOL}\) and \(\mathrm{NPAOL}\) with \[\mathrm{PAOL}\subsetneq \mathrm{NPAOL}\subsetneq P.\]

The present paper is Millennium Problem II in the PFT programme. Its goal is to show that, within the PAL-constrained setting, \(P\) and \(NP\) are structurally separated at the level of the AOL: there are problems that admit PAL-coherent nondeterministic solutions in polynomial time but that cannot be decided by any PAL-coherent deterministic machine in polynomial time.

The canonical example is 3-SAT. Nondeterministic AOL-Machines realise event cascades that branch into exponentially many assignments encoded as coherence-compatible clusters. Deterministic AOL-Machines are confined to a single cascade whose coherence capacity grows only polynomially with input size. The geometric obstruction is that a single PAL-coherent active set cannot encode enough distinguishable assignments to simulate the full nondeterministic search without breaking PAL.

The separation proved here is:

• \(3\)-SAT \(\in \mathrm{NPAOL}\) by a PAL-coherent nondeterministic event-cascade construction;

• \(3\)-SAT \(\notin \mathrm{PAOL}\) because any PAL-coherent deterministic cascade lacks sufficient coherence capacity.

This yields \(P_{\mathrm{PAL}} \neq NP_{\mathrm{PAL}}\) in the coherence-constrained model. The argument depends directly on the CCCT definitions and capacity bounds.

This paper addresses the P versus NP question only within the coherence-constrained AOL-Machine model introduced in CCCT. All separations and constraints discussed here apply exclusively to this model and do not extend to classical Turing computation. In particular, we do not claim a resolution of the classical P versus NP problem as defined by the Clay Mathematics Institute. Classical P versus NP remains open.

Background: PAL, AOL, and CCCT

We recall the core structures from CCCT; full details and proofs are in [1].

Allen Orbital Lattice and PAL

The Allen Orbital Lattice is a hexagonal lattice in the complex plane with vertices \(V\) and edges \(E\) connecting nearest neighbours. A prime indexing \[\sigma : V \to \mathbb{P}\] assigns a distinct prime \(p_v\) to each vertex \(v \in V\). Each active vertex carries a phase \(\theta_t(v) \in [0,2\pi)\) at discrete time \(t\).

The right-hand side is strictly greater than \(-1\) for all finite primes, so antipodal phase differences (\(\pi\)) are forbidden inside a single PAL-coherent active set.

AOL-Machines and Coherence Classes

An AOL-Machine is a computational model whose configurations are PAL-coherent active sets on the AOL with phase labels, updated by a local transition rule. A computation is a finite sequence \[(S_t,\theta_t)_{t=0}^T\] such that \(S_t\) is PAL-coherent for all \(t\).

• \(\mathrm{PAOL}\) consists of languages decided by deterministic PAL-coherent AOL-Machines in time polynomial in the input length.

• \(\mathrm{NPAOL}\) consists of languages decided by nondeterministic PAL-coherent AOL-Machines in polynomial time.

CCCT proves the strict inclusions \[\mathrm{PAOL}\subsetneq \mathrm{NPAOL}\subsetneq P,\] showing that coherence is a third independent resource and that Cobham invariance fails in the PAL-constrained setting.

Here we treat these results as established and focus on their consequences for \(P\) vs. \(NP\).

3-SAT on the Allen Orbital Lattice

We consider 3-SAT as a representative NP-complete problem. An instance consists of a boolean formula \(\varphi\) in conjunctive normal form with \(m\) clauses \(C_j\), each clause containing three literals over \(n\) variables \(x_1,\dots,x_n\). The language 3-SAT is the set of satisfiable formulas.

Encoding Assignments

We encode truth assignments as configurations on the AOL as follows.

• For each variable \(x_i\) we select a vertex \(v_i \in V\) with prime index \(p_{v_i}\).

• A truth assignment \(a \in \{0,1\}^n\) is represented by phases \[\theta_a(v_i) = \begin{cases} 0 &\text{if } a_i = 0,\\ \pi &\text{if } a_i = 1. \end{cases}\]

In this direct encoding, complementary truth values at the same variable correspond to antipodal phases. As established in CCCT, antipodal differences are incompatible with PAL inside a single active region.

Nondeterministic Event Cascades for 3-SAT

A nondeterministic AOL-Machine can realise an event cascade that branches over assignments:

1. Start from an initial PAL-coherent seed \(S_0\) encoding the instance \(\varphi\) and a neutral base phase for all \(v_i\).

2. At each branching step, locally extend the active set to include a coherence-compatible cluster corresponding to a partial assignment. Nondeterministic choices select branches that extend partial assignments in parallel.

3. Enforce clause satisfaction locally: branches that violate a clause are pruned by failing to meet a grounding threshold or by being removed from the active set.

4. Accept if at least one branch reaches a grounded configuration in which all clauses are simultaneously satisfied.

Because the machine is nondeterministic, the global behaviour is defined by the existence of at least one PAL-coherent branch that reaches acceptance in polynomially many steps. Only a single branch needs to be realised in any given run. The event cascade thus explores an exponentially large assignment space in the nondeterministic sense without requiring a single active set to encode all assignments simultaneously.

This yields:

The construction aligns with the usual correspondence between nondeterministic polynomial time and existential search over assignments, with PAL ensuring that each realised branch remains geometrically coherent.

Deterministic PAL Capacity and 3-SAT

We now argue that no PAL-coherent deterministic AOL-Machine can decide 3-SAT in polynomial time. The obstruction is purely geometric.

Single-Cascade Limitation

A deterministic AOL-Machine has a single active cascade \((S_t,\theta_t)_{t=0}^T\) for each input. To decide 3-SAT on all instances of size \(n\) in polynomial time, this cascade must, at some point, encode enough information to distinguish between satisfiable and unsatisfiable formulas with up to \(2^n\) possible assignments.

In standard Turing models, this is possible in principle because the machine can revisit tape cells and reuse space. In the PAL-constrained AOL model, the active set \(S_t\) must remain PAL-coherent, and coherence capacity limits both the size and structure of encodable patterns.

A direct encoding of assignments using antipodal phases is ruled out by the PAL inequality ([eq:pal]): any attempt to simultaneously represent both truth values at the same variable within one active region would violate PAL. More generally, CCCT shows that computations requiring antipodal phase differences between logically linked states in a single coherent region cannot be implemented by AOL-Machines.

Coherence Capacity and Exponential Branching

CCCT establishes that PAL-coherent active sets cannot support exponential branching patterns that differentiate all assignments of a 3-SAT instance while remaining within polynomial resource bounds. Informally:

• Each assignment distinguishes a pattern of phases across the variable vertices.

• Distinguishable assignments require phase patterns that cannot be compressed into a single PAL-coherent cluster once their number exceeds a coherence-dependent capacity.

• This capacity grows subexponentially with \(n\); it is bounded by the prime-indexed structure of the lattice and the PAL inequality.

Thus a deterministic PAL-coherent cascade cannot, in polynomially many steps, construct or traverse a configuration space rich enough to discriminate all satisfiable formulas from all unsatisfiable ones using only one active coherent region.

The detailed argument follows the same geometric pattern as the Cobham-invariance failure proof in CCCT, applied to the exponential assignment structure of 3-SAT instead of parity patterns.

P \(\neq\) NP in the PAL-Constrained Model

We now combine the previous sections.

Interpreting \(\mathrm{PAOL}\) and \(\mathrm{NPAOL}\) as the PAL-constrained analogues of \(P\) and \(NP\), this gives a geometric, lattice-based separation of deterministic and nondeterministic polynomial time. In the language of the Millennium Problems, this is a coherence-constrained resolution of \(P \neq NP\).

Discussion and Outlook

CCCT shows that coherence is a third computational resource alongside time and space. The present paper specialises this to 3-SAT and \(P\) vs. \(NP\):

• Nondeterministic PAL-coherent machines exploit event cascades across the AOL to explore large assignment families in parallel, constrained only by coherence along each realised branch.

• Deterministic PAL-coherent machines are restricted to a single cascade whose coherence capacity grows only polynomially; it cannot realise the exponential branching structure needed for 3-SAT.

• The separation is structural rather than combinatorial: it arises from the geometry of prime-indexed phase space and the PAL inequality.

This coherence-constrained version of \(P \neq NP\) has two readings:

1. As a model-theoretic result: in the AOL-Machine model with PAL, the analogue of \(P\) is strictly smaller than the analogue of \(NP\).

2. As a physical claim: if realistic computation is constrained by PAL-like coherence limits, then nature itself implements a version of \(P \neq NP\) at the substrate level.

The Millennium Problem II statement is that, under the Pattern Field Theory description of structure and coherence, the second reading is the relevant one: the separation is not an artefact of an abstract model but a consequence of the underlying lattice geometry.

Future work in the series will refine the quantitative coherence capacity bounds for specific problem families and connect these results to empirical constraints in physical computing architectures.

This document is part of Pattern Field Theory (PFT) and the Allen Orbital Lattice (AOL). It belongs to the Millennium Problems series and depends directly on the Coherence-Constrained Computation Theory (CCCT) paper, which defines the PAL-constrained complexity hierarchy \(\mathrm{PAOL}\subsetneq \mathrm{NPAOL}\subsetneq P\).

© 2025 James Johan Sebastian Allen — All Rights Reserved.
patternfieldtheory.com

References

1. James Johan Sebastian Allen. Coherence-Constrained Computation Theory (CCCT): A New Axis in Computational Complexity. Pattern Field Theory Papers, November 13, 2025. Available at: https://www.patternfieldtheory.com/papers/ccct_20251113.pdf