P colonies with agent division

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F22%3AA0000910" target="_blank" >RIV/47813059:19240/22:A0000910 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/journal/information-sciences/vol/589/suppl/C" target="_blank" >https://www.sciencedirect.com/journal/information-sciences/vol/589/suppl/C</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ins.2021.12.094" target="_blank" >10.1016/j.ins.2021.12.094</a>

Jazyk výsledku

angličtina

Název v původním jazyce

P colonies with agent division

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

P colonies with agent division

Popis výsledku anglicky

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.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information Sciences

ISSN

0020-0255

e-ISSN

—

Svazek periodika

589

Číslo periodika v rámci svazku

April 2022

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

162-169

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85122240605