Matematické Fórum

Prosím o nápovědu...

Uvažujme problém, jehož instancí je orientovaný graf s vybraným vrcholem v a dále k
‘oblázků’. Můžeme v jakémkoli pořadí provádět následující elementární kroky:
• na vrchol x můžeme položit oblázek, pokud v daný okamžik leží oblázky na všech
vrcholech, z nichž vede hrana do x,
• oblázek položený na vrchol můžeme odebrat (a znovu použít později).
Otázkou je, zda existuje posloupnost kroků, při níž položíme oblázek na zadaný vrchol v.
Prokažte, že problém je v PSPACE.

//na začátku nejsou žádné oblázky v grafu
//jaké by mělo být ověření, konstrukce touringova stroje?
děkuji