Among Open image in new window -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 Open image in new window . 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 Open image in new window , 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 /log where n is the number of variables in the quantified formula given as input.
Solving QSAT in Sublinear Depth
Manzoni, Luca;
2019-01-01
Abstract
Among Open image in new window -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 Open image in new window . 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 Open image in new window , 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 /log where n is the number of variables in the quantified formula given as input.File | Dimensione | Formato | |
---|---|---|---|
(Lecture Notes in Computer Science 11399).pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
305.59 kB
Formato
Adobe PDF
|
305.59 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.