License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.9
URN: urn:nbn:de:0030-drops-99574
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9957/
Go to the corresponding LIPIcs Volume Portal

Rahman, Md Lutfar ; Watson, Thomas

Complexity of Unordered CNF Games

pdf-format:
LIPIcs-ISAAC-2018-9.pdf (0.5 MB)

Abstract

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 variants of this game in which the variables may be played in any order, and each turn consists of picking a remaining variable and a truth value for it.
- For the version where the set of variables is partitioned into two halves and each player may only pick variables from his/her half, we prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for unbounded-width CNFs (Schaefer, STOC 1976).
- For the general unordered version (where each variable can be picked by either player), we also prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for 6-CNFs (Ahlroth and Orponen, MFCS 2012) and PSPACE-complete for positive 11-CNFs (Schaefer, STOC 1976).

BibTeX - Entry

@InProceedings{rahman_et_al:LIPIcs:2018:9957,
  author =	{Md Lutfar Rahman and Thomas Watson},
  title =	{{Complexity of Unordered CNF Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9957},
  URN =		{urn:nbn:de:0030-drops-99574},
  doi =		{10.4230/LIPIcs.ISAAC.2018.9},
  annote =	{Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time}
}

Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI