ON BALANCED VERSUS UNBALANCED COMPUTATION TREES

A great number of complexity classes between P and PSPACE can be defin ed via leaf languages for computation trees of nondeterministic polyno mial-time machines. Jenner, McKenzie, and Therien (Proceedings of the 9th Conference on Structure in Complexity Theory, 1994) raised the iss ue of whether considering balanced or unbalanced trees makes any diffe rence. For a number of leaf-language classes, coincidence of both mode ls was shown, but for the very prominent example of leaf-language clas ses from the alternating logarithmic-time hierarchy the question was l eft open. It was only proved that in the balanced case these classes e xactly characterize the classes from the polynomial-time hierarchy. He re, we show that balanced trees apparently make a difference: In the u nbalanced case, a class from the logarithmic-time hierarchy characteri zes the corresponding class from the polynomial-time hierarchy with a PP-oracle. Along the way, we get an interesting normal form for PP com putations.