论文标题
erdős-Selfridge定理，用于非单调CNF
Erdős-Selfridge Theorem for Nonmonotone CNFs
论文作者
论文摘要
在有影响力的论文中，Erdős和Selfridge在HyperGraph上或同等地在单调CNF上介绍了制造商破坏游戏。玩家轮流为自己选择的变量分配价值，而Breaker的目标是满足CNF，而Maker的目标是伪造它。 Erdős-Selfridge定理说，每个单调CNF中的条款最少，每个条款具有$ k $文字，其中制造商的获胜策略为$θ（2^k）$。 当CNF不一定单调时，我们研究了类似的问题。当制造商播放最后播放时，我们证明了$θ（\ sqrt {2} \，^k）$的界限，而$ω（1.5^k）$和$ o（r^k）$当断路器上次播放时，其中$ r =（1+ \ sqrt {5} {5}）/2 \ of 1.6118 $是Golden $。
In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker's goal is to satisfy the CNF, while Maker's goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with $k$ literals per clause where Maker has a winning strategy is $Θ(2^k)$. We study the analogous question when the CNF is not necessarily monotone. We prove bounds of $Θ(\sqrt{2}\,^k)$ when Maker plays last, and $Ω(1.5^k)$ and $O(r^k)$ when Breaker plays last, where $r=(1+\sqrt{5})/2\approx 1.618$ is the golden ratio.
