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 approximation classes: syntactic and ... more >>>

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

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

• 1-tt-mitoticity and m-mitoticity differ on NP.
• 1-tt-reducibility and m-reducibility differ on NP.
• There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither T-mitotic nor m-mitotic).
... more >>>

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 for any ... more >>>