文章基本信息

标题：Relativized NP Search Problems and Propositional Proof Systems
本地全文：下载
作者：Joshua Buresh-Oppenheim ; Tsuyoshi Morioka
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider Total Functional \NP ( \TFNP ) search problems. Such problems are based on combinatorial principles that guarantee, through locally checkable conditions, that a solution to the problem exists in an exponentially-large domain, and have the property that any solution has a polynomial-size witness that can be verified in polynomial time. These problems can be classified according to the combinatorial principle that guarantees the existence of a solution; for example, \PPP is the class of such problems whose totality is assured by the Pigeonhole Principle. We show many strong connections between relativized versions of these search classes and the computational power---in particular the proof complexity---of their underlying principles. These connections, along with lower bounds in the propositional proof systems Nullstellensatz and bounded-depth LK, allow us to prove several new relative separations among the classes \PLS , \PPP , \PPA , \PPAD , and \PPADS .