DocumentCode :
2200520
Title :
The quantitative structure of exponential time
Author :
Lutz, Jack H.
Author_Institution :
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
fYear :
1993
fDate :
18-21 May 1993
Firstpage :
158
Lastpage :
175
Abstract :
Recent results on the internal, measure-theoretic structure of the exponential time complexity classes E=DTIME(2linear) and E 2=DTIME(2polynomial) are surveyed. The measure structure of these classes is seen to interact in informative ways with bi-immunity, complexity cores, ⩽mP-reducibility, circuit-size complexity, Kolmogorov complexity, and the density of hard languages. Possible implications for the structure of NP are discussed
Keywords :
computational complexity; Kolmogorov complexity; NP; circuit-size complexity; complexity cores; exponential time; exponential time complexity classes; hard languages; measure-theoretic structure; quantitative structure; Circuits; Complexity theory; Computer science; Density measurement; Lifting equipment; NP-complete problem; Polynomials; Time measurement;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
Type :
conf
DOI :
10.1109/SCT.1993.336530
Filename :
336530
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2200520
بازگشت