Хэвлэлийн нэр: Natural Computing, Springer
Зохиогч: И.Цэрэн-Онолт
Хамтран зохиогч: [И.Цэрэн-Онолт:J.SW42]
Хэвлүүлсэн огноо: 2008-04-23
Хуудас дугаар: 519-534
Өгүүллийн хураангуй: We consider the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption that some (possibly exponentially large) pre-computed resources are given in advance. In particular, we propose two uniform families of spiking neural P systems which can be used to address the NP-complete problems sat and 3-sat, respectively. Each system in the first family is able to solve all the instances of sat which can be built using n Boolean variables and m clauses, in a time which is quadratic in n and linear in m. Similarly, each system of the second family is able to solve all the instances of 3-sat that contain n Boolean variables, in a time which is cubic in n. All the systems here considered are deterministic.
Өгүүллийн төрөл: Томсон-Ройтерсийн индекстэй(IF-JCR) сэтгүүл
Өгүүллийн зэрэглэл: Гадаад
Түлхүүр үг: #Pre-computed resources #Mebrane computing