Networks of polarized splicing processors as problem solvers

摘要

In this paper we show how Networks of Polarized Splicing Processors (NPSPs) can be used as problem solvers. We give a detailed uniform solution for the 3-coloring problem using O (m*n) time and we briefly discuss a solution for the 3-SAT problem in O (n*m) time. We also give the complete algorithm that can solve the n-queens completion problem in O (n*(n - m)) time, hence the n-queens problem in O(n(2)) time. All of the solutions use NPSPs with 2 nodes.