This project focuses on the structure of complexity classes that are known to lie between the classes P and PSPACE, on the one hand, and on the circuit complexity classes, on the other hand. Many of the well-studied complexity classes can be specified by considering computation trees and circuits with functions of k- valued logic. It is of interest to learn the power of this method of specification; that is, what classes can or cannot be characterized this way. Specifically, while `leaf languages` have been successfully used in some settings, it is not known how broadly they can be used. Similarly, the study of the structure of the Boolean hierarchy or of the polynomial hierarchy over a complexity class of partitions may yield approaches for studying the Boolean hierarchy on NP or the polynomial-time hierarchy, respectively.
