An Isomorphism between Subexponential and Parameterized Complexity Theory

被引：0

作者：

Chen, Yijia ^{[1
]}

Grohe, Martin ^{[2
]}

机构：

[1] Shanghai Jiao Tong Univ, Dept Comp Sci, BASICS, Shanghai 200030, Peoples R China

[2] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

来源：

CCC 2006: TWENTY-FIRST ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2006年

关键词：

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：314 / +

页数：3

共 16 条

[1] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .4. ON COMPLETENESS FOR W[P] AND PSPACE ANALOGS [J].

ABRAHAMSON, KA ;

DOWNEY, RG ;

FELLOWS, MR .

ANNALS OF PURE AND APPLIED LOGIC, 1995, 73 (03) :235-276

[2]

Alber J, 2001, LECT NOTES COMPUT SC, V2076, P261

[3] An improved deterministic local search algorithm for 3-SAT [J].

Brueggemann, T ;

Kern, W .

THEORETICAL COMPUTER SCIENCE, 2004, 329 (1-3) :303-313

[4] On the existence of subexponential parameterized algorithms [J].

Cai, LM ;

Juedes, D .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) :789-807

[5]

Chen J, 2004, ANN IEEE CONF COMPUT, P150

[6]

CHEN J, 2004, P 36 ACM S THEOR COM, P212

[7] On miniaturized problems in parameterized complexity theory [J].

Chen, YJ ;

Flum, J .

THEORETICAL COMPUTER SCIENCE, 2006, 351 (03) :314-336

[8]

DEMRI S, 2002, LECT NOTES COMPUT SC, V2285, P620

[9]

DOWNEY R, 2003, ELECT NOTES THEORETI, V78, P1

[10]

DOWNEY R, 1999, PARAMETERIZED COMPLE

← 1 2 →