A uniform solution to SAT using membrane creation

DOI10.1016/j.tcs.2006.10.013zbMath1108.68058MaRDI QIDQ870255

Francisco J. Romero-Campero, Mario J. Pérez-Jiménez, Miguel Á. Gutiérrez-Naranjo

Publication date: 12 March 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.013

zbMATH Keywords

SAT problem; membrane computing; natural computing; cellular complexity classes

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

The computational power of timed P systems with active membranes using promoters, Solving SAT with P systems with anti-membranes, On the efficiency of synchronized P systems, Solving 3-SAT in distributed P systems with string objects, Accelerated execution of P systems with active membranes to solve the \(N\)-queens problem, Computational efficiency and universality of timed P systems with membrane creation, Tissue P systems with cell separation: attacking the partition problem, Denotational semantics of membrane systems by using complete metric spaces, Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion, Time-free solution to SAT problem by tissue P systems, Cell-like P systems with evolutional symport/antiport rules and membrane creation, Subroutines in P systems and closure properties of their complexity classes, LOGIC AND ARITHMETIC OPERATIONS WITH A CONSTANT NUMBER OF STEPS IN MEMBRANE COMPUTING

Cites Work

• The power of communication: P systems with symport/antiport
• How to express tumours using membrane systems
• Computing with membranes
• Membrane computing. An introduction.
• A fast \(P\) system for finding a balanced 2-partition
• Membrane Computing
• Unnamed Item