Matematické Fórum

Dobrý den,

potřeboval bych prosím poradit, jak začít s řešením tohoto příkladu, tedy co bych měl udělat pro jeho vyřešení . Nevím si moc rady a tak bych potřeboval trošku popíchnout.

(Problém QBF; Quantified Boolean Formulas)
Uvažujme problém
Název: QBF (problém pravdivosti kvantifikovaných booleovských formulí)
Vstup: formule (∃x1)(∀x2)(∃x3)(∀x4). . .(∃x2n−1)(∀x2n)F(x1, x2, . . . , x2n), kde
F(x1, x2, . . . , x2n) je booleovská formule v konjunktivní normální formě.
Otázka: je daná formule pravdivá ?
Navrhněte algoritmus, který řeší problém QBF a má prostorovou složitost omezenou polynomem. (Tím ukážete, že QBF je v PSPACE.)
Návod. Řekneme, že formule F(x1, x2, . . . , x2n) je OK pro posloupnost booleovských hodnot b1, b2, . . . , bi
, kde 0 ≤ i ≤ 2n, jestliže buď i = 2n a F(b1, b2, . . . , b2n) = true,
nebo i < 2n, i je liché a F je OK jak pro b1, b2, . . . , bi
, true, tak pro b1, b2, . . . , bi
, f alse,
nebo i < 2n, i je sudé a F je OK pro alespoň jednu z posloupností b1, b2, . . . , bi, true a b1, b2, . . . , bi, f alse.

Ověřte nejprve, že formule (∃x1)(∀x2)(∃x3)(∀x4). . .(∃x2n−1)(∀x2n)F(x1, x2, . . . , x2n) je
pravdivá právě tehdy, když F je OK pro prázdnou posloupnost.
Pak sestavte kýžený algoritmus (a prokažte, že jeho prostorová [tedy paměťová] složitost
je polynomiální).