Breaking the Tractability Barrier: A Generic Low-Level Solver for NP-Hard Instances (N=63) on Commodity 64-Bit Silicon
Andrés Sebastián Pirolo · Zenodo (CERN European Organization for Nuclear Research) · 2025
Feedback and independent verification are welcome. Thank you. Abstract: This work presents the experimental validation of a generic low-level hardware architecture designed to achieve tractability beyond state-of-the-art barriers for NP-hard optimization. The system solves Longest Path and Hamiltonian Path instances up to the physical limit of 64-bit registers (N=63 nodes) in sub-second time on a consumer mobile processor. Key Achievements: The 64-Bit Frontier: Successfully solved instances of N=63 (Search space \approx 1.9 X 10^{87} permutations) in 0.673 seconds. Constructive Proof: The complete Hamiltonian path for N=63 is verified and printed, demonstrating 63 unique nodes and zero duplicates. Thermodynamic Invariance: Stress tests confirm bit-perfect determinism even under extreme thermal throttling (80°C), proving the architecture utilizes physical entropy as a computational resource rather than an error source. Methodology: The architecture operates entirely within CPU registers using bitwise operations (AND, OR, XOR, CTZ) and requires zero external memory allocation. It employs a Thermodynamic Chaos Engine to harvest entropy from race conditions and a Prime-Factor Structural Pruning heuristic to reduce the search space by ~97.4% in dense topologies. Conclusion: This work validates that NP-hard industrial optimization is achievable through physics-aware co-design of algorithm and silicon substrate, portable to any modern 64-bit processor (x86, ARM, RISC-V). [email protected]