2022
P colonies with agent division
CIENCIALA, Luděk; Lucie CIENCIALOVÁ and Petr SOSÍKBasic information
Original name
P colonies with agent division
Authors
Edition
Information Sciences, Amsterodam, Netherlands, Elsevier, 2022, 0020-0255
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
is not subject to a state or trade secret
Impact factor
Impact factor: 8.100
Marked to be transferred to RIV
Yes
RIV identification code
RIV/47813059:19240/22:A0000910
Organization unit
Faculty of Philosophy and Science in Opava
UT WoS
EID Scopus
Keywords in English
Membrane Computing; P colony; SAT Problem; Class NP; Class co-NP
Tags
International impact, Reviewed
Changed: 6/3/2023 10:42, Mgr. Kamil Matula, Ph.D.
Abstract
In the original language
P colonies, a variant of membrane (P) systems, are simple cell-inspired multi-agent systems without an inner structure of agents. The agents consist of a single membrane with a fixed number of atomic objects inside. Yet, they have interesting computational properties thanks to the collaboration and coordination of agents. Certain types of P colonies have been previously shown to be computationally complete in the Turing sense. We introduce a new type of rules for P colonies, inspired by the process of cell fission (division). We show that these extended P colonies can deterministically solve the Problem 3-SAT in linear time with respect to the number of clauses of the formula, starting with three agents only. In turn, classes NP and co-NP are solvable in polynomial time by polynomially uniform families of these P colonies. Several open problems arise, among others the possibility of characterization of the borderline between P and NP by certain parameters of P colonies.