\beta_k-Complete Problems and Greediness
Robert Szelepcs enyi · 1993
Kintala and Fischer [1980] defined the limited nondeterminism hierarchy within NP, the so-called \beta hierarchy. \beta_k is the class of languages recognized by polynomial time bounded Turing machines making at most O(\log^k n) nondeterministic moves, where n is the length of the input. .pp It has been conjectured that ``By restricting the amount of nondeterminism in NP-complete problems, we do not seem to obtain complete problems for \beta_k'''' [D\''{i}az and Tor\''{a}n, 1990]. 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 \beta_k by restricting the amount of nondeterminism in NP-complete problems. We also discuss the connections between \beta hierarchy completeness and greedy algorithms; we show that using greediness we can define many complete problems for \beta.