ECCC-Report TR97-006https://eccc.weizmann.ac.il/report/1997/006Comments and Revisions published for TR97-006en-usSun, 27 Apr 1997 08:16:18 +0300
Comment 1
| A correction to Parameterized Parallel Complexity Comment on: TR97-006 |
Marco Cesati,
Miriam Di Ianni
https://eccc.weizmann.ac.il/report/1997/006#comment1A reduction presented in the paper is wrong.
We show a computational problem that replaces
the original one.
Sun, 27 Apr 1997 08:16:18 +0300https://eccc.weizmann.ac.il/report/1997/006#comment1
Paper TR97-006
| Parameterized Parallel Complexity |
Marco Cesati,
Miriam Di Ianni
https://eccc.weizmann.ac.il/report/1997/006We consider the framework of Parameterized Complexity, and we
investigate the issue of which problems do admit efficient fixed
parameter parallel algorithms by introducing two different
degrees of efficiently parallelizable parameterized problems, PNC
and FPP. We sketch both some FPP-algorithms solving natural
parameterized problems and a useful tool for proving membership
to FPP based on the concept of treewidth. We then focus our
attention on parameterized parallel intractability and prove that
a necessary condition for a parameterized problem to be complete
for the class of sequentially fixed parameter tractable problems
is that it is not in NC for some fixed value of the parameter
(unless P = NC). Finally, we give two alternative
characterizations of both PNC and FPP, and we use them to prove
the PNC-completeness of two natural parameterized problems.
Wed, 19 Feb 1997 13:33:10 +0200https://eccc.weizmann.ac.il/report/1997/006