Home

All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size

We present several results concerning the computational power and complexity of Accepting Networks of Splicing Processors (ANSP). We show that every recursively enumerable language can be accepted by an ANSP of size 7 out of which 6 do not depend on the given language. Then we propose a method for constructing, given an NP-language, an ANSP of size 7 accepting that language in polynomial time. Unlike the previous case, all nodes of this ANSP depend on the given language. Since we discuss how each ANSP may be viewed as a problem solver, the later result may be interpreted as a method for solving every NP-problem in polynomial time by an ANSP of size 7. A very recent improvement is finally presented.

Speaker: Victor Mitrana