Quantificatori universali in QBFS

Question

Ho esaminato le riduzioni da / per il linguaggio TQBF e sono riusciti a rimanere bloccati su qualcosa che non è quasi certamente vero (o, se è vero, mi manca un costo computazionale significativo ad esso associato) con rispetto per semplificare le istanze TQBF.

Per la semplicità, limitiamo l'attenzione alle istanze TQBF in prenex forma normale e CNF senza variabili gratuite. La mia ipotesi (che sospetto fortemente è sbagliata, ma non è stata in grado di trovare un contro-esempio) è che un tale TQBF è soddisfacente se e solo se il TQBF che risulta dal rimozione di tutte le istanze di variabili quantificate universalmente dalla frase è soddisfatta. Ad esempio, prendi la seguente istanza:

$ \ esiste un \ forall b \ esiste c \ forlt d $ $ \ PSI (A, B, C , d) $

$ \ psi (a, b, c, d)= (\ neg a \ vee b \ vee c) \ wedge (\ neg b \ vee \ eng c \ vee d) \ wedge (a \ vee c \ vee \ neg d) $

In primo luogo, sostengo che questa istanza non è soddisfatta (facilmente verificabile a mano). Se applichiamo il metodo che descrivo sopra, otteniamo il seguente "core":

$ \ esiste un \ esiste c $ $ \ phi (a, c) $ , < / P >.

$ \ phi (a, c)= (\ neg a \ vee c) \ wedge (\ neg c) \ wedge (a \ vee c) $

che è chiaramente soddisfacente. Se invece di questo esempio guardiamo questo:

$ \ esiste un \ forall b \ esiste c \ forlt d $ $ \ PSI (A, B, C , d) $

$ \ psi (a, b, c, d)= (\ neg a \ vee b \ vee \ neg c) \ wedge (\ neg b \ vee c \ vee d) \ wedge (a \ vee c \ vee \ neg d) $

che chiaramente è soddisfavole (impostato c a true, a to feck) e che ha un "nucleo" di

$ \ esiste un \ esiste c $ $ \ phi (a, c) $ , < / P >.

$ \ phi (a, c)= (\ neg a \ vee \ neg c) \ wedge (c) \ wedge (a \ vee c) $

che è anche soddisfatto con le stesse impostazioni variabili.

Se questo metodo funziona sempre, che sembrerebbe implicare che vi è una riduzione da TQBF a sapersi nel tempo lineare nel numero di quantificatori universali e il numero di occorrenze delle variabili universalmente quantificate nella formula, mostrando che TQBF è NP-Complete (è già noto per essere PSPACE-COMPLETO E quindi NP-HARD, quindi se è in NP è NP-Complete) e inoltre che NP= PSPACE. Sarei assolutamente stordito se questo è il caso, ma non sono stato in grado di trovare un controesempio (o un costo computazionale mancante nella riduzione che non lo rende il tempo polinomiale). Cosa mi manca?

Answer 1

L'intuizione è stata giusta. Non funziona. Ecco un controesempio.

Considerare $ \ Forall A \ esiste B \ Varfi (A, B) $ dove $ \ Varfi (A, b)= (a \ lor \ neg b) \ Land (\ neg a \ lor b) $ . Questa affermazione valuta TRUE.

Tuttavia, se rimuoviamo $ A $ Seguendo la procedura, otteniamo $ \ esiste b \ psi (B) $ dove $ \ PSI (B)= ((\ neg B) \ Land (B)) $ ; E questa affermazione valuta il falso.

Un modo per capire perché il tuo metodo non funziona è che $ \ forlt a \ esiste b \ varphi (a, b) $ non è equivalente a $ \ esiste b \ forlt a \ varphi (a, b) $ . Al massimo del tuo metodo potrebbe funzionare se tutte le $ \ forlt $ siedi all'interno, cioè per una frase del modulo $ \ esiste \ cdots \ esiste \ forall \ cdots \ forlt $ , ma non per nessun altro modello di $ \ esiste $ e $ \ forlt $ .