A special machine for solving NP-complete problems

NP-complete problems, including optimal routing, scheduling and network design, are foundational to essential tasks across various industries. However, they actually pose challenges for conventional electronic computers.

As the magnitude of these problems grows, the time required to find solutions also increase exponentially, restricting the range of feasible computations. Notably, modern electronic computers face difficulties with these problems due to two primary constraints: physical limitations, as silicon chips near atomic scales and quantum effects begin to interfere with their functionality; and architectural limitations inherent in the Turing machine model, which processes data in a linear and sequential manner.

To that end, a recent study led by Professor Jin Xu at Peking University introduced a non-Turing computational model called the Probe Machine, which has been realized in hardware as the Electronic Probe Computer (EPC60). This innovative approach aims to overcome the fundamental limitations of classical architectures, enhancing both accuracy and efficiency in tackling NP-complete problems.

The team published their results in the KeAi journal Fundamental Research.

“Electronic computers are inherently restricted by the Turing model's linear data arrangement and sequential operations, which render large-scale parallel processing impractical for NP problems,” explains Xu. “Our probe machine organizes data into multidimensional units and employs fully parallel probe operators, allowing for the simultaneous exploration of solution paths without delays between operators.”

The three main findings in the study are:

1.   Data and probe libraries: Graphs are classified into four structural categories, each processed using specialized probe operators that perform vertex deletion, contraction, edge addition and Kempe-change operations.

2.   Massive parallelism: Each probe operator runs independently across multiple non-intersecting subgraphs, eliminating idle time between operations and dramatically accelerating search.

3.   Scalable hardware: The system’s modular cabinet design allows seamless expansion by adding standardized probe computing units interconnected via high-speed optical links.

“In performance benchmarks, EPC60 solved 3-coloring problems on 2,000-vertex graphs with 100% accuracy in 3,430 seconds, while Gurobi—a leading commercial solver—achieved only 5–6% accuracy after 43,571 seconds.,” shares Xu. “A particularly challenging instance that stumped Gurobi even after 15 days of computation — EPC60 managed to find valid colorings in under one minute.”

The team highlighted that their findings have moved from this particular topic from a theoretical nature to a that of a deployable machine—one that not only outperforms the best software solvers, but is also inherently scalable. “This marks a turning point in computational intelligence, offering a universal, hardware-based solver for complex problems ranging from supply chain logistics to circuit design,” adds Xu.

The team plans to scale the EPC architecture further and explore its integration into high-performance computing environments for real-time industrial applications.

Contact author: Jin Xu, School of Computer Science, Peking University, Beijing 100871, China, jxu@pku.edu.cn

Funder: This study acknowledges the support by the National Major Research Instrument Development Project (62427811); the Key Program of the National Natural Science Foundation of China (62332006); and the General Program of the National Natural Science Foundation of China (62172014).

Conflict of interest: The authors declare that they have no conflicts of interest in this work.

See the article: Jin Xu, et al., A special machine for solving NP-complete problems. Fundamental Research. Volume 5, issue 2, June 2025, Pages 1743-1749, https://doi.org/10.1016/j.fmre.2025.05.010