La. Hemaspaandra et J. Rothe, UNAMBIGUOUS COMPUTATION - BOOLEAN HIERARCHIES AND SPARSE TURING-COMPLETE SETS, SIAM journal on computing, 26(3), 1997, pp. 634-653
Citations number
62
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
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.