Scholarlink

<p>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 this game is well-understood: it is <Emphasis FontCategory="SansSerif">NL</Emphasis>-complete for 2-CNFs and <Emphasis FontCategory="SansSerif">PSPACE</Emphasis>-complete for 3-CNFs. We continue the study of the <i>unordered</i> 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 <Emphasis FontCategory="SansSerif">L</Emphasis> for 2-CNFs and <Emphasis FontCategory="SansSerif">PSPACE</Emphasis>-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 <Emphasis FontCategory="SansSerif">P</Emphasis>, indeed in <Emphasis FontCategory="SansSerif">L</Emphasis>, 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tractable Unordered 3-CNF Games

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年9月22日

查看全文
  • 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 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.