Time-free solution to SAT problem using P systems with active membranes

DOI10.1016/j.tcs.2013.11.014zbMath1358.68103OpenAlexW1987502316MaRDI QIDQ2440831

Tao Song, Mario J. Pérez-Jiménez, Luis F. Macías-Ramos, Lin-Qiang Pan

Publication date: 19 March 2014

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

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

zbMATH Keywords

membrane computingP systemNP-complete problemtime-free solutionsemi-uniform solution

Mathematics Subject Classification ID

Related Items (16)

An efficient time-free solution to SAT problem by P systems with proteins on membranes ⋮ An efficient time-free solution to QSAT problem using P systems with proteins on membranes ⋮ Solving SAT with P systems with anti-membranes ⋮ Solving 3-SAT in distributed P systems with string objects ⋮ A time-free uniform solution to subset sum problem by tissue P systems with cell division ⋮ Cell-like P systems with evolutional symport/antiport rules and membrane creation ⋮ The computational power of timed P systems with active membranes using promoters ⋮ Computational efficiency and universality of timed P systems with active membranes ⋮ Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion ⋮ Computational efficiency and universality of timed P systems with membrane creation ⋮ Time-free solution to SAT problem by P systems with active membranes and standard cell division rules ⋮ Time-free cell-like P systems with multiple promoters/inhibitors ⋮ Time-freeness and clock-freeness and related concepts in P systems ⋮ P systems attacking hard problems beyond NP: a survey ⋮ P systems based computing polynomials: design and formal verification ⋮ Time-free Solution to Independent Set Problem using P Systems with Active Membranes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trading polarizations for labels in P systems with active membranes
• Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes
• On small universal antiport P systems
• Tissue P systems.
• The computational power of cell division in P systems: Beating down parallel computers?
• Computing with membranes
• Membrane computing. An introduction.
• On the power of membrane division in P systems
• Further remark on P systems with active membranes and two polarizations
• COMPUTATION OF RAMSEY NUMBERS BY P SYSTEMS WITH ACTIVE MEMBRANES
• Computational efficiency of dissolution rules in membrane systems
• Membrane Computing

This page was built for publication: Time-free solution to SAT problem using P systems with active membranes