Journal of Membrane Computing Вычислительная теория и математика

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

David Orellana-Martín, Claudio Zandron, Alberto Leporati
Springer Nature · 2025-05-07 · DOI 10.1007/s41965-025-00190-3

Аннотация

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.

Читать у издателя →