Time-free solution to SAT problem by tissue P systems (Q1992361)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Time-free solution to SAT problem by tissue P systems |
scientific article |
Statements
Time-free solution to SAT problem by tissue P systems (English)
0 references
5 November 2018
0 references
Summary: Tissue P systems are a class of computing models inspired by intercellular communication, where the rules are used in the nondeterministic maximally parallel manner. As we know, the execution time of each rule is the same in the system. However, the execution time of biochemical reactions is hard to control from a biochemical point of view. In this work, we construct a uniform and efficient solution to the \texttt{SAT} problem with tissue P systems in a time-free way for the first time. With the P systems constructed from the sizes of instances, the execution time of the rules has no influence on the computation results. As a result, we prove that such system is shown to be highly effective for NP-complete problem even in a time-free manner with communication rules of length at most 3.
0 references
0 references