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 OX1 3QD, U Department of Computer Science Xiamen University, Xiamen 361005, China

会议类型: 国际会议

会议名称: Asian Conference on Membrane Computing (2012亚洲膜计算国际会议)(ACMC2012)

会议地点: 武汉

会议语种:英文

页码: 74-87

在线出版日期: 2012-10-15（万方平台首次上网日期，不代表论文的发表时间）