<p>SAT is NP-complete, QBF is PSPACE-complete, DQBF is NEXPTIME-complete. Is there any extension of QBF or restriction of DQBF that is EXPTIME-complete?</p>

<p>Added later: a definition of DQBF can be found here: <a href="https://www.react.uni-saarland.de/publications/sat14.pdf">https://www.react.uni-saarland.de/publications/sat14.pdf</a></p>

CC BY-SA 3.0
2015-06-25T09:01:48.650Z
The qustion would be more useful if you added the definition of DQBF, which is probably not familiar to everyone here.
Jan Johannsen
CC BY-SA 3.0
2015-06-25T09:15:58.163Z
This is not quite what you seem to be after, but there are propositional modal logic with an EXP-complete satisfiability problem, such as PDL.
Emil Jeřábek
CC BY-SA 3.0
2015-07-01T18:03:14.477Z
Unfortunately, I cannot find the reference anymore but I remember that deciding the following game is EXPTIME-complete. It is a two-player game played on a (CNF)-formula where the set of variables is partitioned into (X,Y). At their turn, Player 1 (resp. 2) can swap the truth value of one variable in X (resp. Y). They start from a given (non satisfying) assignment and Player 1 wins whenever the formula becomes satisfied (while Player 2 wins if, say, the game cycles or after $2^n$ moves).
user
<cc.complexity-theory>
EXPTIME-complete propositional satisfiability problem
Martin Zimmermann
# EXPTIME-complete propositional satisfiability problem

(Asked by: username_0 on 2015-06-25)

SAT is NP-complete, QBF is PSPACE-complete, DQBF is NEXPTIME-complete. Is there any extension of QBF or restriction of DQBF that is EXPTIME-complete?

Added later: a definition of DQBF can be found here: <https://www.react.uni-saarland.de/publications/sat14.pdf>

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: The qustion would be more useful if you added the definition of DQBF, which is probably not familiar to everyone here.  
> **username_2**: This is not quite what you seem to be after, but there are propositional modal logic with an EXP-complete satisfiability problem, such as PDL.  
> **username_3**: Unfortunately, I cannot find the reference anymore but I remember that deciding the following game is EXPTIME-complete. It is a two-player game played on a (CNF)-formula where the set of variables is partitioned into (X,Y). At their turn, Player 1 (resp. 2) can swap the truth value of one variable in X (resp. Y). They start from a given (non satisfying) assignment and Player 1 wins whenever the formula becomes satisfied (while Player 2 wins if, say, the game cycles or after $2^n$ moves).  

---

## 0 answers

