New Design of P Vs NP Problem in Modern Terminology (2026) — © Hemant Pandey

“The hard part is not making the calculation faster. The hard part is discovering the structure that makes most of the calculation unnecessary.”

© 2026 Hemant Pandey. All rights reserved.

This article documents an original ongoing research framework. It is a research hypothesis and design document, not a claim that P Vs NP has been solved. The mathematical statements explicitly identified as lemmas or conjectures below remain to be proved or falsified.

1. Why redesign the question?

The conventional presentation of combinatorial optimization emphasizes the enormous number of possible solutions. The present research asks a different question: does the apparent combinatorial explosion arise partly because a structured spatial problem is being represented as an unstructured search?

Human observers looking at a large random point set usually notice structure before performing calculations. We see clusters, isolated points, boundaries, symmetry and relative separation. The research program attempts to convert that perceptual compression into formal mathematical invariants and then test whether those invariants can reduce the search for an optimal travelling-salesman tour.

2. Formal problem definition

Let

P_n = {p₁, …, p_n} ⊂ ℝ²

be a finite set of distinct points. Define the complete Euclidean graph

G_n = (P_n, E_n)

with edge length

d_ij = ‖p_i − p_j‖.

A Hamiltonian tour is

T = (p_π(1), p_π(2), …, p_π(n), p_π(1))

where π is a permutation of {1, …, n}. Its objective function is

L(T) = Σ_i=1ⁿ d(p_π(i), p_π(i+1)),

with π(n+1) = π(1).

The global optimum is

L_n* = min_{T ∈ ℋ(Pn)} L(T),

where ℋ(P_n) is the set of Hamiltonian cycles. The set of all optimal tours is

𝒪_n = {T ∈ ℋ(P_n) : L(T) = L_n*}.

There may be more than one member of 𝒪_n. Therefore the target is not a unique tour; it is any member of 𝒪_n.

3. Structural representation: clusters and convex hulls

For a subset C ⊆ P_n, define its convex hull

H(C) = conv(C).

The working hypothesis is that a random spatial distribution often admits a useful hierarchy

points → clusters → convex hulls → nested hulls/polygons → controlled structural extension → local tour transformations.

The convex polygon is treated as a catalyst: it is not assumed to solve TSP by itself. Its proposed role is to reduce the number of meaningful branches that require explicit calculation.

4. Relative separation: converting visual clustering into mathematics

Published perceptual-grouping research makes the term relative distance especially interesting. A human does not need an absolute distance threshold to see that a set of points belongs together. A cluster can remain visually recognizable when the entire diagram is scaled because the relationship between internal and external distances remains similar.

For a candidate cluster C, let s(C) denote a characteristic internal scale. For a point p outside H(C), define

h(p,C) = d(p,H(C))

and the dimensionless candidate separation ratio

ρ(p,C) = h(p,C) / s(C).

This is not yet claimed to be the universal invariant. It is a testable mathematical candidate for the human judgement that a new point is structurally separated from an existing cluster.

5. Controlled addition: the a+b−c operation

Suppose T_n ∈ 𝒪_n and a new point p is added. If p is structurally admissible for controlled extension, it may be inserted into an existing edge (a,b).

The change in tour length is

Δ(a,p,b) = d(a,p) + d(p,b) − d(a,b).

This is the a+b−c operation. It is an optimization/growth operation for adding a new point, not a closed-tour restructuring operation.

6. Closed-tour restructuring: the a+b−c−d operation

For two non-adjacent tour edges (a,b) and (c,d), break both edges and test the possible cross reconnections.

One comparison is

d(a,c) + d(b,d) < d(a,b) + d(c,d),

and the other orientation is

d(a,d) + d(b,c) < d(a,b) + d(c,d).

If either reconnection is shorter, the tour is changed and the process continues. This is the a+b−c−d operation. It is fundamentally different from a+b−c: it is a tour-changing operation on an already closed network.

7. Lemma I — Controlled Extension Lemma

Conjectural statement. For a hierarchically separable Euclidean point set, if T_n ∈ 𝒪_n and a new point p satisfies the structural separation conditions relative to the current network, then at least one globally optimal (n+1)-tour can be obtained by inserting p into an edge of an optimal n-tour and subsequently applying the permitted tour transformations.

Let ℛ(T_n,p) denote the tours reachable from T_n by the permitted insertion and restructuring operations. The desired result is

T_n ∈ 𝒪_n and p admissible ⇒ 𝒪_n+1 ∩ ℛ(T_n,p) ≠ ∅.

This is the formal version of the one-city induction hypothesis. It must be proved or falsified; it cannot be assumed from successful examples.

8. Lemma II — Structural 2-opt Sufficiency Lemma

For arbitrary Euclidean TSP, the statement “no improving 2-opt move exists” does not in general imply global optimality. Therefore the proposed theorem must be restricted to the structurally defined class.

Conjectural statement. For every non-optimal Hamiltonian cycle T in the specified class, there exists an improving admissible two-edge exchange.

Formally,

T ∉ 𝒪_n ⇒ ∃(a,b),(c,d) such that L(T′) < L(T).

If this lemma is proved for the class, then the final complete a+b−c−d sweep has the desired implication:

no improving two-edge exchange ⇒ T ∈ 𝒪_n.

9. Lemma III — Hull/Cluster Preservation Lemma

Conjectural statement. Under the separation conditions defining a new cluster, an optimal tour does not require arbitrary restructuring of the previously optimized cluster. Its interaction with the new cluster can be represented through a bounded structural interface.

The vague intuition “the (n+1)-optimal tour cannot reorganize everything from scratch” must be replaced by a quantitative statement of the form

|E_old \ E_new| ≤ f(I),

where I represents the size or complexity of the interface between the existing hierarchy and the new cluster, and f is a function to be established.

Finding a useful bound for f is one of the central geometric problems of the research.

10. Lemma IV — Controlled Induction

If the Controlled Extension Lemma holds at every admissible stage, then an optimal tour can be propagated through a controlled sequence

T₃ → T₄ → T₅ → … → T_n.

Thus

T₃ ∈ 𝒪₃ ⇒ T_n ∈ 𝒪_n

provided every extension satisfies the hypotheses of the preceding lemmas.

11. What if the next point lies inside the existing structure?

If p ∈ H(C), or if its relative separation ρ(p,C) is insufficient, controlled addition is suspended. The existing network must be re-optimized before controlled growth resumes.

This explains why arbitrary point ordering is fundamentally different from controlled addition. A fixed 12-point dataset can be viewed as 11-point, 10-point and smaller instances, but an arbitrary ordering can introduce a point that is internal to the current geometric structure. In that case the inductive predecessor is no longer guaranteed to be structurally stable.

The proposed algorithm therefore consists of structural epochs rather than blind one-point growth:

stable structure → admissible new cluster/point → controlled extension → local restructuring → stable structure.

12. The polynomial target

For n points there are O(n²) pairs of tour edges. A complete two-edge exchange sweep therefore contains O(n²) elementary comparisons.

If the number of required structural sweeps or transformations can itself be bounded by O(n²), the resulting target complexity is

O(n²) × O(n²) = O(n⁴).

This is presently a complexity target, not an established theorem. The missing statement is itself a lemma:

Polynomial Transformation Bound: the number of structural transformations required to reach an optimum under the proposed hierarchy is polynomially bounded.

13. The complete conjectural framework

The research ultimately seeks to establish the following implication for an appropriately defined class of Euclidean point configurations:

structural recognition + controlled construction + polynomially bounded local restructuring ⇒ an optimal Hamiltonian tour is reachable in polynomial time.

In symbolic form, if S(P_n) denotes the structural hierarchy and ℛ_poly(S) the tours reachable through polynomially many permitted operations, the desired statement is

𝒪_n ∩ ℛ_poly(S(P_n)) ≠ ∅.

The central proof problem is therefore not merely to find a short tour. It is to prove that the structural search space contains at least one global optimum and that it can be traversed in polynomially many operations.

14. Why this is relevant—but not yet sufficient—to P Vs NP

Even a successful polynomial algorithm for a restricted geometric TSP class would not by itself prove P = NP. To obtain a P Vs NP consequence, the result would have to cover a sufficiently general NP-complete problem or provide an appropriate polynomial reduction argument.

The present research therefore treats Euclidean TSP as a laboratory for discovering universal structural invariants. The deeper question is whether the apparent exponential complexity of a problem sometimes disappears when the correct representation is discovered.

15. The research program

1. Formalize relative cluster separation and compare candidate definitions.
2. Compare perceptual proximity models with density-based clustering.
3. Construct convex-hull and nested-hull hierarchies on public Euclidean TSP instances.
4. Test controlled external additions against near-boundary and interior additions.
5. Apply a+b−c only as the controlled growth operation.
6. Apply the complete a+b−c−d sweep as the closed-tour restructuring and final check.
7. Compare every resulting tour against independently certified global optima for small instances.
8. Search deliberately for counterexamples to each lemma.
9. Only after the structural lemmas survive adversarial testing attempt formal proofs.

The guiding principle is simple:

Do not protect the hypothesis. Try to kill it.

16. Copyright and citation

© 2026 Hemant Pandey. All rights reserved.

This article documents an original ongoing research framework and its development. It may be cited for academic, educational or research discussion with attribution to Hemant Pandey and a link to the original publication. Reproduction or republication of the article in whole or substantial part requires permission.

Suggested citation: Pandey, Hemant. (2026). New Design of P Vs NP Problem in Modern Terminology. Ongoing Research Archive.

“The objective is not to prove the hypothesis by force. The objective is to discover the smallest counterexample if it is wrong—and, if it survives, to understand why it survives.”

Research status: ongoing. The lemmas and structural invariants in this document are proposed research targets and are not represented as established mathematical results.