Solution to PSPACE-complete problem using P systems with active membranes with time-freeness
From MaRDI portal
Publication:2298575
Summary: P systems with active membranes are powerful parallel natural computing models, which were inspired by cell structure and behavior. Inspired by the parallel processing of biological information and with the idealistic assumption that each rule is completed in exactly one time unit, P systems with active membranes are able to solve computational hard problems in a feasible time. However, an important biological fact in living cells is that the execution time of a biochemical reaction cannot be accurately divided equally and completed in one time unit. In this work, we consider time as an important factor for the computation in P systems with active membranes and investigate the computational efficiency of such P systems. Specifically, we present a time-free semiuniform solution to the quantified Boolean satisfiability problem (QSAT problem, for short) in the framework of P systems with active membranes, where the solution to such problem is correct, which does not depend on the execution time for the used rules.
Recommendations
- scientific article; zbMATH DE number 2118901
- Time-free solution to SAT problem using P systems with active membranes
- Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
- Time-free solution to independent set problem using P systems with active membranes
- scientific article; zbMATH DE number 1583885
- Time-free solution to SAT problem by P systems with active membranes and standard cell division rules
- Space complexity equivalence of P systems with active membranes and Turing machines
- A new approach for solving SAT by P systems with active membranes
- Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
- Decidability of termination problems for sequential P systems with active membranes
Cites work
- A time-free uniform solution to subset sum problem by tissue P systems with cell division
- Almost sure exponential stability of implicit numerical solution for stochastic functional differential equation with extended polynomial growth condition
- An efficient time-free solution to QSAT problem using P systems with proteins on membranes
- An efficient time-free solution to SAT problem by P systems with proteins on membranes
- Computation of Ramsey numbers by P systems with active membranes
- Computational efficiency and universality of timed P systems with active membranes
- Computational efficiency and universality of timed P systems with membrane creation
- Computing with membranes
- Exact solutions for a Dirac-type equation with N-fold Darboux transformation
- Exponential stabilization of switched time-varying systems with delays and disturbances
- Further remark on P systems with active membranes and two polarizations
- scientific article; zbMATH DE number 1583879 (Why is no real title available?)
- scientific article; zbMATH DE number 5671765 (Why is no real title available?)
- scientific article; zbMATH DE number 1236223 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 2118901 (Why is no real title available?)
- Inference of bounded L systems with polymorphic P systems
- Membrane Computing
- Membrane computing. An introduction.
- Mixed lump-stripe soliton solutions to a dimensionally reduced generalized Jimbo-Miwa equation
- On a class of coupled Hamiltonian operators and their integrable hierarchies with two potentials
- P systems with active membranes: Attacking NP-complete problems
- P systems with minimal parallelism
- P systems with proteins: a new frontier when membrane division disappears
- Planning as quantified Boolean formula
- Reaction systems with influence on environment
- RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
- Riemann-Hilbert approach for an initial-boundary value problem of the two-component modified Korteweg-de Vries equation on the half-line
- Robust QBF Encodings for Sequential Circuits with Applications to Verification, Debug, and Test
- Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes
- Spiking neural P systems
- The computational complexity of tissue P systems with evolutional symport/antiport rules
- The computational power of cell division in P systems: Beating down parallel computers?
- Time-free solution to SAT problem by P systems with active membranes and standard cell division rules
- Tissue P systems.
- Trading polarizations for labels in P systems with active membranes
- Twelve years of QBF evaluations: QSAT is PSPACE-hard and it shows
- Two classes of permutation trinomials with Niho exponents
- Uniform Solution of QSAT Using Polarizationless Active Membranes
Cited in
(27)- Tissue P systems with promoter simulation with MeCoSim and P-Lingua framework
- Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion
- Solving a PSPACE-complete problem with cP systems
- The computational power of cell-like P systems with one protein on membrane
- 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
- Lump solutions and interaction solutions for the dimensionally reduced nonlinear evolution equation
- The computational power of monodirectional tissue P systems with symport rules
- Monodirectional tissue P systems with channel states
- Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division
- Cell-like P systems with evolutional symport/antiport rules and membrane creation
- Prolongation structures and \(N\)-soliton solutions for a new nonlinear Schrödinger-type equation via Riemann-Hilbert approach
- Behavior of the correction equations in the Jacobi-Davidson method
- Cell-like P systems with polarizations and minimal rules
- An efficient time-free solution to QSAT problem using P systems with proteins on membranes
- Time-free solution to SAT problem using P systems with active membranes
- scientific article; zbMATH DE number 1583885 (Why is no real title available?)
- A linear time complexity of breadth-first search using P system with membrane division
- The computational power of timed P systems with active membranes using promoters
- scientific article; zbMATH DE number 2118901 (Why is no real title available?)
- Computational efficiency and universality of timed P systems with active membranes
- Time-free solution to independent set problem using P systems with active membranes
- P systems with active membranes: Trading time for space
- Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
- Spiking neural P systems with lateral inhibition
- Solving 3-SAT in distributed P systems with string objects
- Weighted spiking neural P systems with polarizations and anti-spikes
This page was built for publication: Solution to PSPACE-complete problem using P systems with active membranes with time-freeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2298575)
