Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Antimatter as a Frontier of Tractability in Membrane Computing

Díaz-Pernil D., Peña-Cantillana F., Alhazov A., Freund R., Gutiérrez-Naranjo M. A.

Fundamenta Informaticae

2014

Vol. 134, nr 1/2

83--96

It is well known that the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary and nonelementary membranes is exactly the complexity class P (see [9], Theorem 2). In this paper, we prove that if such a P systems model is endowed with antimatter and annihilation rules, then NP problems can be solved, even without non-elementary membrane division. In this way, antimatter is shown to be a frontier of tractability in Membrane Computing.