Effectively Polynomial Simulations

摘要

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.