J 2022

P colonies with agent division

CIENCIALA, Luděk; Lucie CIENCIALOVÁ a Petr SOSÍK

Základní údaje

Originální název

P colonies with agent division

Autoři

CIENCIALA, Luděk; Lucie CIENCIALOVÁ a Petr SOSÍK

Vydání

Information Sciences, Amsterodam, Netherlands, Elsevier, 2022, 0020-0255

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Odkaz na domovskou stránku časopisu s výsledkem, Odkaz na plný text výsledku

Impakt faktor

Impact factor: 8.100

Označené pro přenos do RIV

Ano

Kód RIV

RIV/47813059:19240/22:A0000910

Organizační jednotka

Filozoficko-přírodovědecká fakulta v Opavě

DOI

https://doi.org/10.1016/j.ins.2021.12.094

UT WoS

000807272800009

EID Scopus

2-s2.0-85122240605

Klíčová slova anglicky

Membrane Computing; P colony; SAT Problem; Class NP; Class co-NP

Štítky

2022, RIV2022, SGS112019, ÚI

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 6. 3. 2023 10:42, Mgr. Kamil Matula, Ph.D.

Anotace

V originále

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.
Zobrazeno: 18. 11. 2026 15:38