Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-011 | 2nd January 2006 00:00

An Isomorphism between Subexponential and Parameterized Complexity Theory

RSS-Feed




TR06-011
Authors: Yijia Chen, Martin Grohe
Publication: 20th January 2006 05:50
Downloads: 3928
Keywords: 


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.



ISSN 1433-8092 | Imprint