ECCC-Report TR19-160https://eccc.weizmann.ac.il/report/2019/160Comments and Revisions published for TR19-160en-usTue, 12 Nov 2019 00:26:59 +0200
Paper TR19-160
| Tractable Unordered 3-CNF Games |
Md Lutfar Rahman,
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/160The 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 this game is well-understood: it is NL-complete for 2-CNFs and PSPACE-complete for 3-CNFs.
We continue the study of the unordered variant of this game, in which each turn consists of picking any remaining variable and assigning it a truth value. The complexity of deciding who can win on a given CNF is less well-understood; prior work by the authors showed it is in L for 2-CNFs and PSPACE-complete for 5-CNFs. We conjecture it may be efficiently solvable on 3-CNFs, and we make progress in this direction by proving the problem is in P, indeed in L, for 3-CNFs with a certain restriction, namely that each width-3 clause has at least one variable that appears in no other clause. Another (incomparable) restriction of this problem was previously shown to be tractable by Kutz.Tue, 12 Nov 2019 00:26:59 +0200https://eccc.weizmann.ac.il/report/2019/160