Published June 30, 2022 | Version v1
Publication

P systems with evolutional symport and membrane creation rules solving QSAT

Description

P systems are computing devices based on sets of rules that dictate how they work. While some of these rules can change the objects within the system, other rules can even change the own structure, like creation rules. They have been used in cell-like membrane systems with active membranes to efficiently solve NP-complete problems. In this work, we improve a previous result where a uniform family of P systems with evolutional communication rules whose left-hand side (respectively, right-hand side) have most 2 objects (resp., 2 objects) and membrane creation solved SAT efficiently, and we obtain an efficient solution to solve QBF-SAT or QSAT (a PSPACE-complete problem) having at most 1 object (respectively, 1 object) in their left-hand side (resp., right-hand side) and not making use of the environment

Abstract

Ministerio de Ciencia e Innovación TIN2017-89842-P

Additional details

Identifiers

URL
https://idus.us.es/handle//11441/134814
URN
urn:oai:idus.us.es:11441/134814

Origin repository

Origin repository
USE