A solution to SAT with virus machines with pre-computed resources

Abstract In Natural Computing, different real-life processes can appear as the inspiration for a new model of computation. Virus machines use the spread and replication of biological viruses as an inspiration for a model of computation with three well-differentiated graphs: the hosts graph, that acts like the memory; the instructions graph, that acts as a program; and the instructions-channel graph, that controls the flow of information through the system. In previous works, the computational power and problem-solving capabilities of this model have been demonstrated. In this work, we provide an application for solving the problem in polynomial time using an EXP -uniform family of super virus machines with OR channel parallelism.