Effectively Polynomial Simulations

Toniann Pitassi, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationInnovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings
Pages370-381
Number of pages12
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Effectively Polynomial Simulations'. Together they form a unique fingerprint.

Cite this