Data Structures and Algorithms

Previous months:
2025 - 2504(2) - 2505(1)

Recent submissions

Any replacements are listed farther down

[3] ai.viXra.org:2505.0045 [pdf] submitted on 2025-05-07 20:09:10

A Formal Proof of P ̸= NP: Self-Referential Complexity and Computational Limits

Authors: Javier Muñoz de la Cuesta
Comments: 19 Pages.

This article presents a formal proof that P ̸= NP, resolving one of the Clay Mathematics Institute’s Millennium Prize Problems. We introduce self-referential complexity, a measure of the computational cost when a deterministic algorithm verifies its own states. Applying this to the NP-complete Boolean SatisfiabilityProblem (SAT), we demonstrate that any deterministic algorithm requires a superpolynomial number of self-referential steps in the worst case, establishing an intrinsic barrier separating P from NP. The proof includes formal definitions, step-by-step mathematical derivations, examples, counterexamples, simulations, and verification conditions, with implications for complexity theory, cryptography, and the foundations of computation.
Category: Data Structures and Algorithms

[2] ai.viXra.org:2504.0103 [pdf] submitted on 2025-04-26 17:33:27

Invariance of Initial Conditions in P and NP and Structural Incompatibility Between Problems with Hypothetical "Additional Hidden Properties" Allowing Partial Solutions to Each

Authors: Dobri Bozhilov
Comments: 10 Pages. (Note by ai.viXra.org Admin: An abstract is required in the article)

The P versus NP problem is traditionally approached through attempts to either construct a polynomial-time algorithm for an NP-complete problem or prove its impossibility. In this work, we propose an alternative approach by exploring a structural contradiction between the hidden properties that would hypothetically enable efficient solutions to different NP-complete problems. We show that if a hidden numerical property (X) exists to solve the Subset Sum Problem (SSP) efficiently, and a distinct combinatorial property (Y) exists to solve the Knapsack Problem (KP) efficiently, the two properties would fundamentally contradict each other. Furthermore, we analyze the role of the Turing Machine model, demonstrating that hidden properties inaccessible to the machine cannot reduce complexity within the standard NP framework. This structural incompatibility supports the conclusion that P ≠ NP, not because no "shortcut" exists, but because the computational model itself prevents the exploitation of any such shortcut without changing the nature of the problems.
Category: Data Structures and Algorithms

[1] ai.viXra.org:2504.0013 [pdf] submitted on 2025-04-03 15:29:48

Selective GC Zoning for Dynamic Compatibility in Static Languages: A Case Study for Mojo

Authors: YoungGwan Jung
Comments: 8 Pages.

Modern languages like Mojo strive to combine Python syntax compatibility with static, high-performance execution. However, dynamic features such as 'eval()' and 'globals()', which involve runtime object creation, mutable scopes, and potential cyclic references, are naturally at odds with a strictly static memory model. To address this challenge, this paper proposes **Selective GC Zoning**, a strategy that isolates dynamic features within a dedicated garbage-collected subspace (GC Zone), while preserving the static memory model for the rest of the code. This design enables near-native performance for general Mojo code while allowing selective Python compatibility for specific dynamic features. In addition, we discuss object escape constraints between static and GC-managed regions, concurrency scenarios, different GC algorithm choices, and future extensions of this approach.
Category: Data Structures and Algorithms

Replacements of recent Submissions

None