Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with canonical pairs:
TR04-106 | 19th November 2004
Christian Glaßer, Alan L. Selman, Liyu Zhang

Canonical Disjoint NP-Pairs of Propositional Proof Systems

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... more >>>

TR07-018 | 1st March 2007
Christian Glaßer, Alan L. Selman, Liyu Zhang

The Informational Content of Canonical Disjoint NP-Pairs

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

ISSN 1433-8092 | Imprint