A Polynomial Time Solution to Constraint Satisfaction Problems by Neural-like P Systems
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. To solve CSPs, 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 inter-cellular communication of neuron cells is presented as a model for solving CSPs. Neural-like P systems are nets 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 even without the ability of cell division or cell separation.
Constraint satisfaction problem Membrane system Neural-like P system NP-hard problem
Lei Xu Xiangxiang Zeng Peter Jeavons
Department of Computer Science,University of Oxford Wolfson Building,Parks Road,Oxford OXI 3QD,UK Department of Computer Science Xiamen University,Xiamen 361005,China
国际会议
成都
英文
74-87
2013-11-04（万方平台首次上网日期，不代表论文的发表时间）