Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
The Informational Content Of Canonical Disjoint Np-Pairs, Christian Glaßer, Alan L. Selman, Liyu Zhang
The Informational Content Of Canonical Disjoint Np-Pairs, Christian Glaßer, Alan L. Selman, Liyu Zhang
Computer Science Faculty Publications and Presentations
We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between propositional proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.
Q1: For which propositional proof systems f and g does the implication hold, and for which does it fail?
Q2: For which propositional proof systems of different strengths are the canonical pairs equivalent?
Q3: What do (non-)equivalent canonical pairs tell about the corresponding propositional proof systems?
Q4: Is every NP-pair (A, B), where A is NP-complete, strongly many-one equivalent to the …