DocumentCode :
2142420
Title :
Two queries
Author :
Buhrman, Harry ; Fortnow, Lance
Author_Institution :
CWI, Amsterdam, Netherlands
fYear :
1998
fDate :
15-18 Jun 1998
Firstpage :
13
Lastpage :
19
Abstract :
We consider the question whether two queries to SAT are as powerful as one query. We show that if PNP[1]=PNP[2] then; locally either NP=coNP or NP has polynomial-size circuits; PNP=PNP[1]; Σ2p=UPNP[1]∩RPNP[1] ; PH=BPPNP[1]. Moreover we extend work of E. Hemaspaandra et al. (1997) to show that if P(Σ2p [1])=P(Σ2p[2]) then Σ2p2p. We also give a relativized world where PNP[1]=PNP[2] but NP≠coNP
Keywords :
computational complexity; SAT; polynomial-size circuits; queries; relativized world; Circuits; Computational modeling; Computer science; Electrical capacitance tomography; History; Polynomials; Turing machines; Uniform resource locators; World Wide Web;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on
Conference_Location :
Buffalo, NY
ISSN :
1093-0159
Print_ISBN :
0-8186-8395-3
Type :
conf
DOI :
10.1109/CCC.1998.694586
Filename :
694586
Link To Document :
بازگشت