DocumentCode :
2931916
Title :
The density of weakly complete problems under adaptive reductions
Author :
Lutz, Jack H. ; Zhao, Yong
Author_Institution :
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
fYear :
1997
fDate :
24-27 Jun 1997
Firstpage :
111
Lastpage :
120
Abstract :
Given a real number α<1, every language that is weakly ⩽nα/2-TP-hard for E or weakly ⩽nα-TP-hard for E2 is shown to be exponentially dense. This simultaneously strengthens results of J.H. Lutz and E. Mayordomo (1994) and B. Fu (1995)
Keywords :
computational complexity; adaptive reductions; computational complexity; real number; weakly complete problems; Circuits; Computational complexity; Computer science; Lifting equipment; Polynomials;
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.612306
Filename :
612306
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2931916
بازگشت