My specific question is the following. Consider the following problem that I call Strange-TQBF:

there is a Boolean function $f(x_1, \ldots, x_n)$ and two players Alice and Bob.

They take turns selecting variables and assigning values to them. After $n$ steps Alice wins if the value of $f$ (according to the assignment) is equal to $1$ and loses otherwise.

It is possible to determine the winner in this game in time $3^n \cdot \text{poly}(n)$ by using dynamic programming. The idea is to solve this problem for all subgames.

Questions: Is there an algorithm that solves the problem in time $3^{n- \varepsilon} \cdot \text{poly}(n)$?

Is it possible to prove that there is no algorithm that solves this problem in time $2^{n+\varepsilon}>0$ under some hypothesis like SETH?

Also, a general question:

Are there any results in fine-grained complexity for games? Can we prove (under some assumptions) for some game that the best possible way to solve the game is just to consider all sub-games?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.