Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

Хэвлэлийн нэр: Theoretical Computer Science, Elsevier

Зохиогч:  И.Цэрэн-Онолт

Хамтран зохиогч: [И.Цэрэн-Онолт:J.SW42],A.Leporati,L.Pan,X.Zeng,X.Zang

Хэвлүүлсэн огноо: 2010-05-28

Хуудас дугаар: 2345-2358

Өгүүллийн хураангуй: In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.

Өгүүллийн төрөл: Томсон-Ройтерсийн индекстэй(IF-JCR) сэтгүүл

Өгүүллийн зэрэглэл: Гадаад

Түлхүүр үг: #Natural computing #Spiking neural P systems

Хавсаргасан файл:


Өгүүлэл нэмсэн: И.Цэрэн-Онолт

Монгол Улсын Шинжлэх Ухаан Технологийн Их Сургууль © 2019