DValue for Boolean games is EXP-complete

Egor Ianovski

We show that the following problem is EXP-complete: given a rational v and a two player, zero-sum Boolean game G determine whether the value of G is at least v. The proof is via a translation of the proof of the same result for Boolean circuit games in Feigenbaum et al. (1995).

Knowledge Graph



Sign up or login to leave a comment