Time-Free Solution to SAT Problem by Tissue P Systems
Joint Authors
Luo, Yueguo
Xiong, Zhongyang
Zhang, Guanghua
Source
Mathematical Problems in Engineering
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-8, 8 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-02-23
Country of Publication
Egypt
No. of Pages
8
Main Subjects
Abstract EN
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 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.
American Psychological Association (APA)
Luo, Yueguo& Xiong, Zhongyang& Zhang, Guanghua. 2017. Time-Free Solution to SAT Problem by Tissue P Systems. Mathematical Problems in Engineering،Vol. 2017, no. 2017, pp.1-8.
https://search.emarefa.net/detail/BIM-1189575
Modern Language Association (MLA)
Luo, Yueguo…[et al.]. Time-Free Solution to SAT Problem by Tissue P Systems. Mathematical Problems in Engineering No. 2017 (2017), pp.1-8.
https://search.emarefa.net/detail/BIM-1189575
American Medical Association (AMA)
Luo, Yueguo& Xiong, Zhongyang& Zhang, Guanghua. Time-Free Solution to SAT Problem by Tissue P Systems. Mathematical Problems in Engineering. 2017. Vol. 2017, no. 2017, pp.1-8.
https://search.emarefa.net/detail/BIM-1189575
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1189575