DocumentCode :
2929675
Title :
Six hypotheses in search of a theorem
Author :
Buhrman, Harry ; Fortnow, L. ; Torenvliet, Leen
Author_Institution :
CWI, Amsterdam, Netherlands
fYear :
1997
fDate :
24-27 Jun 1997
Firstpage :
2
Lastpage :
12
Abstract :
We consider the following six hypotheses: *P=NP. *SAT is truth-table reducible to a P-selective set. *SAT is truth-table reducible to a k-approximable set for some k. *FP||NP =FPNP[log] *SAT is O(log n)-approximable. *Solving SAT is in P on formulae with at most one assignment. We discuss their importance and relationships among them
Keywords :
computational complexity; *P=NP; P-selective set; k-approximable set; truth-table reducible; Analog computers; Computer science; Helium; Polynomials; USA Councils; Uniform resource locators;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 1997. Proceedings., Twelfth Annual IEEE Conference on (Formerly: Structure in Complexity Theory Conference)
Conference_Location :
Ulm
ISSN :
1093-0159
Print_ISBN :
0-8186-7907-7
Type :
conf
DOI :
10.1109/CCC.1997.612295
Filename :
612295
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2929675
بازگشت