Now showing items 21-25 of 25

    • IconSubroutines in P Systems and Closure Properties of Their Complexity Classes  [Presentation]

      Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio (Fenix Editora, 2017)
      The literature on membrane computing describes several variants of P systems whose complexity classes C are "closed under exponentiation", that is, they satisfy the inclusion PC C, where PC is the class of problems ...
    • IconThe Computational Power of Exponential-Space P Systems with Active Membranes  [Presentation]

      Alhazov, Artiom; Leporati, Alberto; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio (Fénix Editora, 2012)
      We show that exponential-space P systems with active membranes characterize the complexity class EXPSPACE. This result is proved by simulating Turing machines working in exponential space via uniform families of P systems ...
    • IconThree Quantum Algorithms to Solve 3-SAT  [Presentation]

      Leporati, Alberto; Felloni, Sara (Fénix Editora, 2006)
      We propose three quantum algorithms to solve the 3-SAT NP-complete decision problem. The first algorithm builds, for any instance Á of 3-SAT, a quantum Fredkin circuit that computes a superposition of all classical ...
    • IconTuring Incompleteness of Asynchronous P Systems with Active Membranes  [Presentation]

      Leporati, Alberto; Manzoni, Luca; Porreca, Antonio E. (Fénix Editora, 2013)
      We prove that asynchronous P systems with active membranes without divi- sion rules can be simulated by place/transition Petri nets, and hence are computationally weaker than Turing machines. This result holds even if ...
    • IconUniform solutions to SAT and Subset Sum by spiking neural P systems  [Article]

      Leporati, Alberto; Mauri, Giancarlo; Zandron, Claudio; Paun, Gheorghe; Pérez Jiménez, Mario de Jesús (Springer, 2009)
      We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this ...