A uniform solution to SAT using membrane creation

DOI10.1016/J.TCS.2006.10.013MaRDI QIDQ870255zbMATH OpenOpenAlexFDO

Authors Mario J. Pérez-Jiménez, Francisco J. Romero-Campero, Miguel A. 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

membrane computingnatural computingSAT problemcellular complexity classes

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Membrane Computing
• A new approach for solving SAT by P systems with active membranes
• Solving SAT with P systems with anti-membranes
• Uniform Solution of QSAT Using Polarizationless Active Membranes
• Time-free solution to SAT problem using P systems with active membranes
• scientific article; zbMATH DE number 1958491
• An efficient time-free solution to SAT problem by P systems with proteins on membranes
• Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
• Solving HPP and SAT by P systems with active membranes and separation rules
• Time-free solution to SAT problem by P systems with active membranes and standard cell division rules

Cites work

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

Cited in

(16)

• Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion
• Solving 3-SAT in distributed P systems with string objects
• Accelerated execution of P systems with active membranes to solve the N-queens problem
• Membrane Computing
• Time-free solution to SAT problem by tissue P systems
• Subroutines in P systems and closure properties of their complexity classes
• On the efficiency of synchronized P systems
• Computational efficiency and universality of timed P systems with membrane creation
• Cell-like P systems with evolutional symport/antiport rules and membrane creation
• Solving SAT with P systems with anti-membranes
• Tissue P systems with cell separation: attacking the partition problem
• Denotational semantics of membrane systems by using complete metric spaces
• Membrane creation and symport/antiport rules solving QSAT
• The power of synchronizing rules in membrane computing
• The computational power of timed P systems with active membranes using promoters
• Logic and arithmetic operations with a constant number of steps in membrane computing

This page was built for publication: A uniform solution to SAT using membrane creation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870255)