UNAMBIGUOUS COMPUTATION - BOOLEAN HIERARCHIES AND SPARSE TURING-COMPLETE SETS

It is known that for any class C closed under union and intersection, the Boolean closure of C, the Boolean hierarchy over C, and the symmet ric difference hierarchy over C all are equal. We prove that these equ alities hold for any complexity class closed under intersection; in pa rticular, they thus hold for unambiguous polynomial time (UP). In cont rast to the NP case, we prove that the Hausdorff hierarchy and the nes ted difference hierarchy over UP both fail to capture the Boolean clos ure of UP in some relativized worlds. Karp and Lipton proved that if n ondeterministic polynomial time has sparse Turing-complete sets, then the polynomial hierarchy collapses. We establish the first consequence s from the assumption that unambiguous polynomial time has sparse Turi ng-complete sets: (a) UP subset of or equal to Low(2), where Low(2) is the second level of the low hierarchy, and (b) each level of the unam biguous polynomial hierarchy is contained one level lower in the promi se unambiguous polynomial hierarchy than is otherwise known to be the case.