Solution to PSPACE-Complete Problem Using P Systems with Active Membranes with Time-Freeness

Abstract EN

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.