DocumentCode
2346009
Title
An isomorphism between subexponential and parameterized complexity theory
Author
Chen, Yijia ; Grohe, Martin
Author_Institution
Dept. of Comput. Sci., Shanghai Jiaotong Univ.
fYear
0
fDate
0-0 0
Lastpage
330
Abstract
We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories
Keywords
computational complexity; exponential time complexity; miniaturization mapping; parameterized complexity theory; reduction preserving isomorphism; subexponential complexity; Algorithm design and analysis; Complexity theory; Computer science; Length measurement; NP-complete problem; Polynomials; Robustness; Size measurement; Time measurement;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
Conference_Location
Prague
ISSN
1093-0159
Print_ISBN
0-7695-2596-2
Type
conf
DOI
10.1109/CCC.2006.8
Filename
1663747
Link To Document