Uniform Solutions to SAT and 3-SAT by Spiking Neural P systems with Pre-computed Resources

Хэвлэлийн нэр: 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

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

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