UNAMBIGUOUS COMPUTATION - BOOLEAN HIERARCHIES AND SPARSE TURING-COMPLETE SETS

Citation
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
Journal title
ISSN journal
00975397
Volume
26
Issue
3
Year of publication
1997
Pages
634 - 653
Database
ISI
SICI code
0097-5397(1997)26:3<634:UC-BHA>2.0.ZU;2-5
Abstract
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.