All reports by Author Md Lutfar Rahman:

__
TR20-097
| 30th June 2020
__

Md Lutfar Rahman, Thomas Watson#### 6-Uniform Maker-Breaker Game Is PSPACE-Complete

__
TR19-160
| 10th November 2019
__

Md Lutfar Rahman, Thomas Watson#### Tractable Unordered 3-CNF Games

__
TR18-039
| 23rd February 2018
__

Md Lutfar Rahman, Thomas Watson#### Complexity of Unordered CNF Games

Revisions: 1

Md Lutfar Rahman, Thomas Watson

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains ... more >>>

Md Lutfar Rahman, Thomas Watson

The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in ... more >>>

Md Lutfar Rahman, Thomas Watson

The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>>