34 citations · 121 across the 14 of their papers we have counts for
4 papers · 1 filter
Unconventional complexity classes in unconventional computing (extended abstract)
Antonio E. Porreca
Many unconventional computing models, including some that appear to be quite different from traditional ones such as Turing machines, happen to characterise either the complexity c…
Characterizing PSPACE with shallow non-confluent P systems
Alberto Leporati, Luca Manzoni, Giancarlo Mauri +2
In P systems with active membranes, the question of understanding the power of non-confluence within a polynomial time bound is still an open problem. It is known that, for shallow…
Solving QSAT in sublinear depth
Alberto Leporati, Luca Manzoni, Giancarlo Mauri +2
Among -complete problems, QSAT, or quantified SAT, is one of the most used to show that the class of problems solvable in polynomial time by families of a given va…
A Turing machine simulation by P systems without charges
Alberto Leporati, Luca Manzoni, Giancarlo Mauri +2
It is well known that the kind of P systems involved in the definition of the P conjecture is able to solve problems in the complexity class by leveraging the uniformi…