We know various types of polynomial-time reductions such as Karp-Levin reductions (many-one reductions), Cook reductions (adaptive Turing reductions), and truth-table reductions (nonadaptive reductions). Each reduction defines a completeness notion in NP. One of the interesting questions in structural complexity is whether these, seemingly different, completeness notions are indeed different. A positive answer immediately implies P not equal to NP . So the goal is to separate the various notions of NP-completeness under the hypothesis P not equal to NP . However, we are far away from proving it. In this talk, I will talk about some strong hypotheses under which we can show various NP-completeness notions are different. The hypotheses involve assumptions about the hardness of computing accepting computations of NP machines and the existence of almost-everywhere hard languages in NP. This is a joint work with Alan Selman.