Abstract
The central conjecture of parameterized complexity states that FPT !=W[1], and is generally regarded as the parameterized counterpart to P !=NP. We revisit the issue of the plausibility of FPT !=W[1], focusing on two aspects: the difficulty of proving the conjecture (assuming it holds), and how the relation between the two classes might differ from the one between P and NP.
Regarding the first aspect, we give new evidence that separating FPT from W[1] would be considerably harder than doing the same for P and NP. Our main result regarding the relation between FPT and W[1] states that the closure of W[1] under relativization with FPToracles is precisely the class W[P], implying that either FPT is not low for W[1], or the WHierarchy collapses. This theorem also has consequences for the AHierarchy (a parameterized version of the Polynomial Hierarchy), namely that unless W[P] is a subset of some level A[t], there are structural differences between the AHierarchy and the Polynomial Hierarchy. We also prove that under the unlikely assumption that W[P] collapses to W[1] in a specific way, the collapse of any two consecutive levels of the AHierarchy implies the collapse of the entire hierarchy to a finite level; this extends a result of Chen, Flum, and Grohe (2005).
Finally, we give weak (oraclebased) evidence that the inclusion W[t]subseteqA[t] is strict for t>1, and that the WHierarchy is proper. The latter result answers a question of Downey and Fellows (1993).
BibTeX  Entry
@InProceedings{bottesch:LIPIcs:2018:9655,
author = {Ralph Christian Bottesch},
title = {{On W[1]Hardness as Evidence for Intractability}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {73:173:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9655},
URN = {urn:nbn:de:0030drops96559},
doi = {10.4230/LIPIcs.MFCS.2018.73},
annote = {Keywords: Parameterized complexity, Relativization}
}
Keywords: 

Parameterized complexity, Relativization 
Collection: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 
Issue Date: 

2018 
Date of publication: 

27.08.2018 