Solving Two-Player Games under Progress Assumptions
summary
Considers augmented games (G, Φ, ψ) with Φ and ψ as LTL over vertices and shows solving them equals solving (G, ψ ⇒ Φ) but complexity depends on assumption class. Live edges and colive edges preserve base game complexity so they are “for free”; their products also remain free. Splitting yields live groups, which make reachability NP-hard and in fact NP-complete, while arbitrary LTL assumptions can blow up to double-exponential complexity. Introduces persistent live groups (sequential use, linear iterations) that again preserve complexity.
AI-written summary · about
chapters (9)
- 0:00Two-player games under progress
- 2:27Why progress assumptions needed
- 4:20Reachability and parity games formalized
- 6:05Complexity with arbitrary assumptions
- 7:09Live edges solved for free
- 9:37Product with live edges and groups
- 13:29Co-live edges efficiency
- 15:54Persistent live groups for controllers
- 19:00Summary and future directions