The complexity of Solitaire
The complexity of Solitaire
复制标题
纸牌的复杂性
DOI：
10.1016/j.tcs.2009.08.027
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
P. McKenzie
中科院分区：
文献类型：
--
作者：
L. Longpré;P. McKenzie
Klondike是几乎每台计算机上都可以使用的着名52张纸牌纸牌游戏。确定一个n-卡克朗代克初始配置是否可以导致胜利的问题是NP完全的。当只允许三个花色而不是通常的四个花色时，问题仍然是NP完全的。当只有两套相反颜色的花色可用时，问题被证明是NL-困难的。当仅有的两个花色具有相同的颜色时，两个限制分别显示在AC 0和NL中。当允许单花色时，问题的复杂性下降到AC 0 [3]，也就是说，问题可以通过一族常数深度无界扇入{and，or，mod 3}-电路来解决。其他情况下进行了研究：例如，“没有国王”的变种与任意数量的花色相同的颜色和一个空的“桩”是NL完全的。
Klondike is the well-known 52-card Solitaire game available on almost every computer. The problem of determining whether an n-card Klondike initial configuration can lead to a win is shown NP-complete. The problem remains NP-complete when only three suits are allowed instead of the usual four. When only two suits of opposite color are available, the problem is shown NL-hard. When the only two suits have the same color, two restrictions are shown in AC0and in NL respectively. When a single suit is allowed, the problem drops in complexity down to AC0[3], that is, the problem is solvable by a family of constant-depth unbounded-fan-in {and, or, mod3}-circuits. Other cases are studied: for example, “no King” variant with an arbitrary number of suits of the same color and with an empty “pile” is NL-complete.