Published November 21, 2019
| Version v1
Publication
A new perspective on computational complexity theory in Membrane Computing
Description
A single Turing machine can solve decision problems with an in nite number
of instances. On the other hand, in the framework of membrane computing, a \solution"
to an abstract decision problem consists of a family of membrane systems (where each
system of the family is associated with a nite set of instances of the problem to be
solved). An interesting question is to analyze the possibility to nd a single membrane
system able to deal with the in nitely many instances of a decision problem.
In this context, it is fundamental to de ne precisely how the instances of the problem
are introduced into the system. In this paper, two different methods are considered:
pre-computed (in polynomial time) resources and non-treated resources.
An extended version of this work will be presented in the 20th International Conference
on Membrane Computing.
Abstract
Ministerio de Economía, Industria y Competitividad TIN2017-89842-PAdditional details
Identifiers
- URL
- https://idus.us.es/handle//11441/90405
- URN
- urn:oai:idus.us.es:11441/90405