A Solution for All-SAT Problem Based on P Systems
Obtaining all of the truth assignments of SAT is called All-SAT and it has numerous applications in artificial intelligence and computer theories. Many algorithms about SAT have been built, but how to solve All-SAT is still difficult. P system is a kind of distributed parallel computing
device of a biochemical type, and membrane division is one of frequently investigated way for obtaining exponential working space in a leaner time (membranes can be repeatedly divided to 2
n
ones in n steps). In this paper, we give a family of uniform P systems with
active membranes and polarizations to solve All-SAT problem simultaneously in polynomial time. Instances show that our P systems can provide all solutions for SAT problems effectively in a distributed and parallel manner.
Keywords: All-SAT Problem; Membrane Computing; P System; SAT Problem
Document Type: Research Article
Affiliations: 1: College of Computer Science and Technology, Zhejiang University, Hangzhou, Zhejiang, 310058, China 2: College of Computer Science, Chongqing University, Chongqing 400044, China 3: Department of Software Engineering, Chongqing College of Electronic Engineering, Chongqing 401331, China
Publication date: 01 July 2016
- Journal of Computational and Theoretical Nanoscience is an international peer-reviewed journal with a wide-ranging coverage, consolidates research activities in all aspects of computational and theoretical nanoscience into a single reference source. This journal offers scientists and engineers peer-reviewed research papers in all aspects of computational and theoretical nanoscience and nanotechnology in chemistry, physics, materials science, engineering and biology to publish original full papers and timely state-of-the-art reviews and short communications encompassing the fundamental and applied research.
- Editorial Board
- Information for Authors
- Submit a Paper
- Subscribe to this Title
- Terms & Conditions
- Ingenta Connect is not responsible for the content or availability of external websites
- Access Key
- Free content
- Partial Free content
- New content
- Open access content
- Partial Open access content
- Subscribed content
- Partial Subscribed content
- Free trial content