A Perfect Path to Computational Biology and Quantum Computing

Celina M.H. de Figueiredo

Published May 31, 2025• 0 citations

Abstract

I revisit my contributions to the P versus NP millennium problem and the computational complexity of combinatorial problems, especially those arising in Computational Biology and Quantum Computing, through 20 PhD theses, mine and of my students. I explain how the dichotomy NP-complete versus polynomial-time of long-standing problems together with their multivariate analysis is settled. Yet, intriguing questions remain.

Related papers

Decoding P vs. NP: A Multidimensional Exploration

Iago Gaspar

The P vs. NP problem is a central open question in theoretical computer science, asking whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. This paper presents an interdisciplinary exploration of this problem by integrating mathematical analysis, quantum computing, and machine learning.We analyze the limitations of polynomial-time reductions among NP-complete problems under the Exponential Time Hypothesis (ETH), providing detailed proofs that offer new insights into the structural complexities within NP. Additionally, we develop a novel quantum-classical hybrid algorithm that combines Grover's algorithm with classical heuristics to solve specific instances of NP-complete problems more efficiently. This includes a comprehensive complexity analysis, scalability discussions, and detailed practical implementation aspects such as oracle constructions.Furthermore, we propose a machine learning framework based on Graph Neural Networks (GNNs) to capture patterns within NP-complete problems. This approach is theoretically justified, enhances heuristic methods, and demonstrates superior performance through extensive experimental comparisons with classical heuristics and exact solvers.By integrating these methods, this work offers fresh perspectives on the P vs. NP problem and contributes to the broader understanding of computational complexity.

Jan 10, 20250 citations

Quantum Computation, Data Science, Bell Games

Richard David Gill

I draw attention to statistical and probabilistic and computer science aspects of the very, very close by topic of quantum internet.

arXiv:2111.07881Harvard Data Science ReviewJan 27, 20220 citations

The complexity of divisibility

Johannes Bausch, Toby S. Cubitt

We address two sets of long-standing open questions in linear algebra and probability theory, from a computational complexity perspective: stochastic matrix divisibility, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic matrices is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e. the quantum analogue of stochastic matrices. We further prove a complexity hierarchy for the divisibility and decomposability of probability distributions, showing that finite distribution divisibility is in P, but decomposability is NP-hard. For the former, we give an explicit polynomial-time algorithm. All results on distributions extend to weak-membership formulations, proving that the complexity of these problems is robust to perturbations.

arXiv:1411.7380Linear Algebra and its ApplicationsApr 8, 201611 citations

One complexity theorist's view of quantum computing

Lance Fortnow

Theoretical Computer ScienceJan 1, 200379 citations

Solving in the quantum computer every classical NP problem in polynomial time

Fernando Maroto

This paper has been withdrawn by the author due to a crucial error in eq.59. I apologize for the inconveniences.

arXiv:quant-ph/9801036Jan 16, 19980 citations

SMT-VOL7 & STCT-VOL3: THE ROUGH PATH TO COMPLEXITY: P = NP VIA CRITICAL ROUGHNESS AND PATH SIGNATURES

Seonggil Lee

The P versus NP problem stands as the foundational challenge of theoretical computer science and computational complexity. Traditional approaches attempt to resolve the question by treating computation purely as discrete Boolean logic operations over finite symbolic strings. In this paper, we establish that NP-hardness is not an arbitrary logical obstacle, but the exact computational manifestation of the physical and geometric phase space of the universe. Utilizing High-Resolution Quantum Field Theory (HR-QCFT), Rough Operator Algebra (ROA), and the Seonggil Theory of Composite Torsion (STCT), we prove that the non-satisfiable constraints of NP-complete problems are isomorphic to the macroscopic topological scar Rdefect generated by the zero-divisor collapse from 16-dimensional sedenions (S) tooctonions (O). By mapping deterministic algorithms onto rough differential equations driven by paths of vanishing H¨older continuity α_n → 0, we demonstrate that any polynomial-timeheuristic algorithm must truncate the infinite-dimensional High-Tensor signature algebra. Crucially, due to the non-associative G_2-triality of STCT, the non-vanishing Associator anomaly exponentially amplifies truncation errors via non-commutative arithmetic friction η. This forces the algorithmic transition operator ˆMTuring into spectral instability, resulting in a total determinant collapse det( ˆM_Turing) = 0. Consequently, we prove P ̸ = NP as an absolute geometric law governing the computational manifold of the physical universe.

Apr 27, 20260 citations