bk-complete problems and greediness

Abstract

Kintala and Fischer [7] defined the limited nondeterminism hierarchy within NP, the so called b  hierarchy. bk is the class of languages recognized by polynomial time bounded Turing machines that make at most O(logk n) nondeterministic moves, where n is the length of the input.

It has been conjectured that "by restricting the amount of nondeterminism in NP-complete problems, we do not seem to obtain complete problems for bk [4]". We demonstrate that this statement is incorrect under what seems to us to be  the natural interpretation of the term "restricting the amount of nondeterminism". We develop the concept of limited nondeterminism-preserving reductions, and obtain complete problems for bk by restricting the amount of nondeterminism in NP-complete problems. We also discuss the connections between b hierarchy completeness and greedy algorithms; we show that using greediness we can define many complete problems for b.