Buhrman, Harry; Spaan, Edith; Torenvliet, Leen Bounded reductions. (English) Zbl 0788.68049 Ambos-Spies, Klaus (ed.) et al., Complexity theory. Current research. Proceedings of the workshop on structure and complexity held at the Dagstuhl International Conference and Research Center, Wadern, Germany, February 2-8, 1992. Cambridge: Cambridge University Press. 83-99 (1993). Summary: 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.For the entire collection see [Zbl 0782.00046]. Cited in 4 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03D15 Complexity of computation (including implicit computational complexity) Keywords:separation of complexity classes; bounded reductions; completeness; nondeterministic time classes; exponential time PDFBibTeX XMLCite \textit{H. Buhrman} et al., in: Complexity theory. Current research. Proceedings of the workshop on structure and complexity held at the Dagstuhl International Conference and Research Center, Wadern, Germany, February 2-8, 1992. Cambridge: Cambridge University Press. 83--99 (1993; Zbl 0788.68049)