Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

The study of the approximability properties of NP-hard

optimization problems has recently made great advances mainly due

to the results obtained in the field of proof checking. In a

recent breakthrough the APX-completeness of several important

optimization problems is proved, thus reconciling `two distinct

views of ...
more >>>

Vikraman Arvind, Jacobo Toran

We relate the existence of disjunctive hard sets for NP to

other well studied hypotheses in complexity theory showing

that if an NP-complete set or a coNP-complete set is

polynomial-time disjunctively reducible

to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using

a similar argument we obtain also that ...
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 >>>

Jacobo Toran

We show that several reducibility notions coincide when applied to the

Graph Isomorphism (GI) problem. In particular we show that if a set is

many-one logspace reducible to GI, then it is in fact many-one AC^0

reducible to GI. For the case of Turing reducibilities we show that ...
more >>>

John Hitchcock, Hadi Shafei

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>