On the computational complexity of spiking neural P systems

DOI10.1007/S11047-010-9213-1MaRDI QIDQ609034zbMATH OpenOpenAlexFDO

Authors Turlough Neary

Publication date 30 November 2010

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.0928

zbMATH Keywords

computational complexityspiking neural P systemlinear timesmall universal spiking neural P systemtime efficient spiking neural P system

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: It is shown that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in linear time and has only 10 neurons.

Recommendations

• On the Computational Complexity of Spiking Neural P Systems
• Computability of spiking neural P systems with anti-spikes
• Polynomial complexity classes in spiking neural P systems
• On spiking neural P systems
• Spiking neural P systems: theoretical results and applications
• On the computational power of circuits of spiking neurons
• Spiking Neural P Systems: Some Characterizations
• Solving Numerical NP-Complete Problems with Spiking Neural P Systems
• Computational power of sequential spiking neural P systems with multiple channels

Cites work

• A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems
• Counter machines and counter languages
• Small universal register machines
• Smaller universal spiking neural P systems
• Solving Numerical NP-Complete Problems with Spiking Neural P Systems
• Spiking neural P systems

Cited in

(17)

• Time features in the computational power of spiking neural P systems
• Small SNQ P systems with multiple types of spikes
• Universality of SNQ P systems using one type of spikes and restrictive rule application
• Universality of graph-controlled leftist insertion-deletion systems with two states
• Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits
• On spiking neural P systems and partially blind counter machines
• On the Computational Complexity of Spiking Neural P Systems
• Three small universal spiking neural P systems
• On the Computational Power of Threshold Circuits with Sparse Activity
• Polynomial complexity classes in spiking neural P systems
• Universal Sleptsov net
• Computing the Maximum Bisimulation with Spiking Neural P Systems
• Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources
• On solutions and representations of spiking neural P systems with rules on synapses
• Novel systematic mathematical computation based on the spiking frequency gate (SFG): innovative organization of spiking computer
• scientific article; zbMATH DE number 19763 (Why is no real title available?)
• Sequentiality induced by spike number in SNP systems: small universal machines

This page was built for publication: On the computational complexity of spiking neural P systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q609034)