Among PSPACE-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 variant of P systems includes the whole PSPACE. However, most solutions require a membrane nesting depth that is linear with respect to the number of variables of the QSAT instance under consideration. While a system of a certain depth is needed, since depth 1 systems only allows to solve problems in P#P, it was until now unclear if a linear depth was, in fact, necessary. Here we use P systems with active membranes with charges, and we provide a construction that proves that QSAT can be solved with a sublinear nesting depth of order nlog n, where n is the number of variables in the quantified formula given as input.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2019). Solving QSAT in Sublinear Depth. In Membrane Computing 19th International Conference, CMC 2018, Dresden, Germany, September 4–7, 2018, Revised Selected Papers (pp.188-201). Springer Nature Switzerland [10.1007/978-3-030-12797-8_13].

Solving QSAT in Sublinear Depth

Leporati, A;Manzoni, L;Mauri, G;Porreca, AE;Zandron, C
2019

Abstract

Among PSPACE-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 variant of P systems includes the whole PSPACE. However, most solutions require a membrane nesting depth that is linear with respect to the number of variables of the QSAT instance under consideration. While a system of a certain depth is needed, since depth 1 systems only allows to solve problems in P#P, it was until now unclear if a linear depth was, in fact, necessary. Here we use P systems with active membranes with charges, and we provide a construction that proves that QSAT can be solved with a sublinear nesting depth of order nlog n, where n is the number of variables in the quantified formula given as input.
slide + paper
QSAT, PSPACE-complete
English
19th International Conference on Membrane Computing, CMC 2018 - 4 September 2018 through 7 September 2018
2018
Hinze, Th; Rozenberg, G; Salomaa, A; Zandron, C
Membrane Computing 19th International Conference, CMC 2018, Dresden, Germany, September 4–7, 2018, Revised Selected Papers
978-3-030-12796-1
2019
11399 LNCS
188
201
none
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2019). Solving QSAT in Sublinear Depth. In Membrane Computing 19th International Conference, CMC 2018, Dresden, Germany, September 4–7, 2018, Revised Selected Papers (pp.188-201). Springer Nature Switzerland [10.1007/978-3-030-12797-8_13].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/233344
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
Social impact