A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules

DOI10.1016/J.TCS.2023.113974MaRDI QIDQ6162071zbMATH OpenOpenAlexFDO

Authors Zsolt Gazdag, Károly Hajagos

Publication date 15 June 2023

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

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

zbMATH Keywords

membrane computingsatisfiability problemP-completenessactive membranesdissolution rules

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Recommendations

• Unconventional Computation
• Sublinear-space P systems with active membranes
• P Systems with Elementary Active Membranes: Beyond NP and coNP
• Remarks on the computational power of some restricted variants of P systems with active membranes
• Membrane Computing

Cites work

• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• scientific article; zbMATH DE number 5671765 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 7298595 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A Characterisation of NL Using Membrane Systems without Charges and Dissolution
• A Turing machine simulation by P systems without charges
• A new method to simulate restricted variants of polarizationless P systems with active membranes
• A polynomial complexity class in P systems using membrane division
• Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P
• Membrane Computing
• Membrane Dissolution and Division in P
• Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems
• On uniformity within \(NC^ 1\)
• P systems attacking hard problems beyond NP: a survey
• P systems with active membranes: Attacking NP-complete problems
• Polarizationless P systems with active membranes: computational complexity aspects
• Remarks on the computational power of some restricted variants of P systems with active membranes
• Seeking computational efficiency boundaries: the Păun's conjecture
• Simulating Turing machines with polarizationless P systems with active membranes
• Solving a special case of the P conjecture using dependency graphs with dissolution
• Sublinear-space P systems with active membranes
• The computational power of membrane systems under tight uniformity conditions
• Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems

Cited in

(2)

• Universal enzymatic numerical P systems with small number of enzymatic rules
• Unary resolution: characterizing \textsc{Ptime}

This page was built for publication: A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules

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