On the Power of Polynomial Time Bit-Reductions Extended Abstract
Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner · 1993
For a nondeterministic polynomial time Turing machine M and an input string x, the leaf string of M on x is the 0-1-sequence of leaf-values (0 ¸ reject, 1 ¸ accept) of the computation tree of M with input x. The set A is said to be bit-reducible to B if there exists an M as above such that for every input x, x is in A if and only if the leaf string of M on x is in B. A class C is definable via leaf language B, if C is the class of all languages that are bit-reducible to B. We are interested in the question how complex a leaf language must be in order to characterize some given class C. This question leads to the examination of the closure of different language classes under bit-reduci...