A Polynomial-Time Solution to Constraint Satisfaction Problems by Neural-like P Systems
Lei Xu, Xiangxiang Zeng and Peter Jeavons
A large number of problems in Artificial Intelligence and other areas of Computer Science can be viewed as special cases of the Constraint Satisfaction Problem (CSP). Generally, solving the CSP is NP-hard, and many different approaches have been developed. In this paper, a novel computing model, a class of neural-like membrane systems (neural-like P systems) which is inspired by the graph-like structure and intercellular communication of biological neurons is presented as a model for solving CSPs. Neural-like P systems are networks of cells (neurons) working with multisets or strings. By broadcasting symbol-impulses to neighbor cells and processing multisets or strings of symbol-impulses from neighbor cells, neural-like P systems can solve the CSP in polynomial time without using cell division or cell separation.
Keywords: Constraint satisfaction problem, membrane systems, neural-like P systems, NP-hard problem.