Uniform solution to Subset Sum by means of virus machines

Abstract Unconventional computing plays an important role in computational complexity theory, providing unconventional computing paradigms to tighten the gap between tractable and presumable intractable problems; however, most unconventional paradigms reach similar gaps and their perspective may become stagnant. In this work, we develop a new outlook by a young natural computing paradigm called virus machines (VMs) which takes inspiration from the biological virus life cycle. A new computational complexity theory through VM is developed by attacking a classical NP-complete problem, the Subset Sum problem. It has been uniformly solved by means of deterministic VM. The uniform construction consists of three different modules: one module B for selecting the possible subset; another module $$Y_j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Y</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:math> that encodes the selection, adds it or not to the final sum, and compares the result; and one last module END to reach the halting configuration and make the output consistent. This design provides a new perspective for solving presumably hard problems by means of families of VMs, opening new research lines in this framework.