All reports by Author Liyu Zhang:

__
TR07-018
| 1st March 2007
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### The Informational Content of Canonical Disjoint NP-Pairs

__
TR06-090
| 22nd June 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang#### Non-Mitotic Sets

__
TR05-072
| 11th July 2005
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems

__
TR05-068
| 7th July 2005
__

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang#### Redundancy in Complete Sets

__
TR05-011
| 21st December 2004
__

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang#### Autoreducibility, Mitoticity, and Immunity

__
TR04-106
| 19th November 2004
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Canonical Disjoint NP-Pairs of Propositional Proof Systems

__
TR03-011
| 17th February 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang#### Disjoint NP-Pairs

Christian Glaßer, Alan L. Selman, Liyu Zhang

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 >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>

<ul>

<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>

<li>1-tt-reducibility and m-reducibility differ on NP.</li>

<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>

Christian Glaßer, Alan L. Selman, Liyu Zhang

We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.

more >>>Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

autoreducible.

Complete sets of any level of PH, MODPH, or

the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>Christian Glaßer, Alan L. Selman, Liyu Zhang

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 >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

We study the question of whether the class DisNP of

disjoint pairs (A, B) of NP-sets contains a complete pair.

The question relates to the question of whether optimal

proof systems exist, and we relate it to the previously

studied question of whether there exists ...
more >>>