Juan Manuel Dato Ruiz, Spain

Nowadays, computational processes are increasingly parallelizable, with particular relevance to problems in the complexity class P—those solvable efficiently by sequential algorithms. Traditionally, many problems in P were considered inherently sequential and resistant to effective parallelization. This work clarifies the roles of classes P, NC (Nick’s Class, representing highly parallelizable problems), and CC (Comparator Circuit Class) in computational complexity, presenting constructive methods that systematically transform canonical sequential algorithms into ultra-efficient parallel solutions. Moreover, the author critically examines existing proofs in the complexity field, highlighting the importance of analyzing their mutual compatibility to advance theoretical foundations. Through novel ultra-parallelization techniques, we demonstrate that any problem efficiently solvable in P can be systematically mapped to a form analogous to NC or CC, drastically reducing computation time and overcoming the established divide between sequential and parallel computation. These transformations enable recasting virtually any efficiently solvable problem as an ultra-efficient parallel algorithm, opening new perspectives in algorithmic design and performance. Finally, the author includes a concise workflow at the end of the essay, which visually outlines the key steps required to transform a problem from class P into class CC, providing a practical roadmap for applying the theoretical methods discussed.

Comparator Circuit Class (CC), Highly Parallelizable Problems (Nick’s Class), Polynomial Time Problems (P), Parallel Random Access Machine Model (PRAM), Nondeterministic Polynomial Problems (NP), Nondeterministic Logarithmic Space Problems (NLOG)