Complexity of Unordered CNF Games

DOI10.1145/3397478MaRDI QIDQ5053069zbMATH OpenOpenAlexFDO

Authors

Publication date 5 December 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3397478

zbMATH Keywords

CNFgameslinear timePSPACE-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Games involving topology, set theory, or logic (91A44)

Recommendations

• Complexity of unordered CNF games
• Unordered constraint satisfaction games
• Tractable unordered 3-CNF games
• The complexity of constraint satisfaction games and QCSP
• The complexity of recursion theoretic games
• On the complexity of counter reachability games
• On the Complexity of Counter Reachability Games
• Mathematical Foundations of Computer Science 2005
• On Complexity of Ehrenfeucht-Fraïssé Games
• On complexity of Ehrenfeucht-Fraïssé games

Cited in

(9)

• Tractable unordered 3-CNF games
• \(2^{3}\) quantified Boolean formula games and their complexities
• Unordered constraint satisfaction games
• scientific article; zbMATH DE number 2086402 (Why is no real title available?)
• Complexity of unordered CNF games
• Mathematical Foundations of Computer Science 2003
• Solving Maker-Breaker games on 5-uniform hypergraphs is PSPACE-complete
• 6-uniform maker-breaker game is PSPACE-complete
• An improved upper bound on the threshold bias of the Oriented-cycle game

This page was built for publication: Complexity of Unordered CNF Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5053069)