On W[1]-Hardness as Evidence for Intractability

Author Ralph Christian Bottesch



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.73.pdf
  • Filesize: 498 kB
  • 15 pages

Document Identifiers

Author Details

Ralph Christian Bottesch
  • University of Innsbruck, Innrain 52, 6020 Innsbruck, Austria

Cite AsGet BibTex

Ralph Christian Bottesch. On W[1]-Hardness as Evidence for Intractability. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.73

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 FPT-oracles is precisely the class W[P], implying that either FPT is not low for W[1], or the W-Hierarchy collapses. This theorem also has consequences for the A-Hierarchy (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 A-Hierarchy 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 A-Hierarchy 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 (oracle-based) evidence that the inclusion W[t]subseteqA[t] is strict for t>1, and that the W-Hierarchy is proper. The latter result answers a question of Downey and Fellows (1993).

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Parameterized complexity
  • Relativization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. E. Allender. Limitations of the upward separation technique. Mathematical Systems Theory, 24(1):53-67, 1991. Google Scholar
  2. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge, 2009. Google Scholar
  3. R.V. Book, C.B. Wilson, and M. Xu. Relativizing time, space, and time-space. SIAM J. Comput., 11(3):571-581, 1982. Google Scholar
  4. R.C. Bottesch. Relativization and Interactive Proof Systems in Parameterized Complexity Theory. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume 89, pages 9:1-9:12, 2018. URL: http://drops.dagstuhl.de/opus/volltexte/2018/8571.
  5. J.F. Buss and T. Islam. Simplifying the Weft hierarchy. Theoretical Computer Science, 351(3):303-313, 2006. Google Scholar
  6. L. Cai, J. Chen, R.G. Downey, and M.R. Fellows. On the structure of parameterized problems in NP. Information and Computation, 123:38-49, 1995. Google Scholar
  7. Y. Chen, J. Flum, and M. Grohe. Machine-based methods in parameterized complexity theory. Theoretical Computer Science, 339:167-199, 2005. Google Scholar
  8. R.G. Downey and M.R. Fellows. Fixed-parameter tractability and completeness III - Some structural aspects of the W hierarchy. In K. Ambos-Spies, S. Homer, and U. Schoning, editors, Complexity Theory, pages 166-191. Cambridge University Press, 1993. Google Scholar
  9. R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer, Berlin, 1999. Google Scholar
  10. R.G. Downey and M.R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  11. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2006. Google Scholar
  12. L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28(5):249-251, 1988. Google Scholar
  13. R. Imagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  14. D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-71, 2011. Google Scholar
  15. C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  16. A. Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail