Back to Search Start Over

AN ISOMORPHISM BETWEEN SUBEXPONENTIAL AND PARAMETERIZED COMPLEXITY THEORY.

Authors :
Yijia Chen
Martin Grohe
Source :
SIAM Journal on Computing. 2007, Vol. 37 Issue 4, p1228-1258. 31p. 1 Diagram.
Publication Year :
2007

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. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*THEORY of constraints
*ALGORITHMS
*ISOMORPHISM (Crystallography)
*ISOMORPHISM (Mathematics)
*CARTOGRAPHY
*ANALYTIC mappings
*MINIATURE electronic equipment
*SET theory
*AGGREGATED data

Details

Language :
English
ISSN :
00975397
Volume :
37
Issue :
4
Database :
Academic Search Index
Journal :
SIAM Journal on Computing
Publication Type :
Academic Journal
Accession number :
27872700
Full Text :
https://doi.org/10.1137/070687153
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details