Comparison of reductions and completeness notions

[PostScript | PDF]

Abstract

We study the question of whether various polynomial-time reductions and the completeness notions differ in NP. We mention known results and give some proof ideas.