Bounded Reductions

We study properties of resource-- and otherwise bounded reductions and corresponding completeness notions on nondeterministic time classes which contain exponential time. As it turns out, most of these reductions can be separated in the sense that their corresponding completeness notions are different. There is one notable exception. On nondeterministic exponential time, 1-truth table and many-one completeness is the same notion. 1 Introduction Efficient reducibilities and completeness are two of the central concepts of complexity theory. Since the first use of polynomial time bounded Turing reductions by Cook [4] and the introduction of polynomial time bounded many-one reductions by Karp[6], considerable effort has been put in the investigation of properties and the relative strengths of different reductions and corresponding completeness notions. In 1975, Ladner, Lynch and Selman [8] gave an extensive survey of different types of reductions and differences between these reductions o..