Effectively Polynomial Simulations
Effectively Polynomial Simulations
复制标题
有效的多项式模拟
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Santhanam
中科院分区：
文献类型：
--
作者：
T. Pitassi;R. Santhanam
我们引入了一个更一般的概念，证明系统之间的有效模拟，我们称之为有效p模拟。我们认为，这一概念是更自然的复杂性理论的观点，并通过重新审视标准的概念，在这方面，我们得到了一些令人惊讶的新结果。首先，我们给出了几个例子，其中有效p模拟是可能的不同的命题证明系统之间，但p模拟是不可能的（有时在复杂性假设下）。其次，我们证明了量化命题逻辑（QBF）的相当弱的证明系统G0可以有效地模拟QBF的任何证明系统。因此，我们的定义揭示了新的光的比较证明力系统。我们也给出了一些证据，相对于弗雷格和扩展弗雷格系统，一个有效的p模拟可能是不可能的。最后，我们证明了有效p模拟，自动化，和P与NP问题之间的新关系。
We introduce a more general notion of efficient simulation between proof systems, which we call effectively-p simulation. We argue that this notion is more natural from a complexity-theoretic point of view, and by revisiting standard concepts in this light we obtain some surprising new results. First, we give several examples where effectively-p simulations are possible between different propositional proof systems, but where p-simulations are impossible (sometimes under complexity assumptions). Secondly, we prove that the rather weak proof system G0 for quantified propositional logic (QBF) can effectively-p simulate any proof system for QBF. Thus our definition sheds new light on the comparative power of proof systems. We also give some evidence that with respect to Frege and Extended Frege systems, an effectively-p simulation may not be possible. Lastly, we prove new relationships between effectively-p simulations, automatizability, and the P versus NP question.