Symmetric Complementation
Symmetric Complementation
复制标题
对称互补
DOI：
10.1145/62.322436
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
J. Reif
中科院分区：
文献类型：
--
作者：
J. Reif
本文介绍了一类完全信息的一人对策，我们称之为互补对策，允许局中人采取补充连续局中人的行动。互补博弈是对称的，如果所有非互补移动都是可逆的（即，形成对称关系）。这些游戏自然与我们称之为同步完成机的一类机器有关。[刘易斯和Papadimitriou，80]研究了对称非确定性机器;它们与我们的对称互补机器相同，只允许在终止时进行互补移动。（即将出现的一篇配套论文描述了对称互补机和交替机的计算复杂性。特别感兴趣的是复杂性类~，CSYMITORY，其中包含的结果问题的对称互补游戏与恒定的补充约束与游戏的位置编码在日志空间中，和下一个移动关系可计算的日志空间。本文证明了限制量化布尔逻辑~，QBFG的判定问题在~，CSYM中是完备的。我们还表明，~，CSYMSTARY包含许多众所周知的和常见的组合问题：
This paper introduces a class of 1 player games of perfect information, which we call complementing games; the player is allowed moves which complement the value of successive plays. A complementing game is symmetric if all noncomplement moves are reversible (i.e., form a symmetric relation). These games are naturally related to a class of machines we call synznetric oomplementing machines. Symmetric nondeterministic machines were studied in [Lewis and Papadimitriou, 80]; they are identical to our symmetric complementing machines with complement moves allowed only on termination. (A companion paper to appear describes the computational complexity of symmetric complementing and alternating machines.) Of particular interest is the complexity class ~,CSYMLOG, which contains the outcome problem of symmetric complementing games with constant complement bound with game positions encoded in log space, and next move relations computable in log space. We show that the decision problem for a restricted quantified Boolean logic ~,QBFG is complete in ~,CSYMLOG. We also show that ~,CSYMLOG contains many well-known and common combinatorial problems: