Document Open Access Logo

Relativization and Interactive Proof Systems in Parameterized Complexity Theory

Author Ralph Bottesch

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.9.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Ralph Bottesch

Cite AsGet BibTex

Ralph Bottesch. Relativization and Interactive Proof Systems in Parameterized Complexity Theory. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.IPEC.2017.9

Abstract

We introduce some classical complexity-theoretic techniques to Parameterized Complexity. First, we study relativization for the machine models that were used by Chen, Flum, and Grohe (2005) to characterize a number of parameterized complexity classes. Here we obtain a new and non-trivial characterization of the A-Hierarchy in terms of oracle machines, and parameterize a famous result of Baker, Gill, and Solovay (1975), by proving that, relative to specific oracles, FPT and A[1] can either coincide or differ (a similar statement holds for FPT and W[P]). Second, we initiate the study of interactive proof systems in the parameterized setting, and show that every problem in the class AW[SAT] has a proof system with "short" interactions, in the sense that the number of rounds is upper-bounded in terms of the parameter value alone.
Keywords
  • Parameterized complexity
  • Relativization
  • Interactive Proof Systems

Metrics

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

References

  1. S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1), 2009. Google Scholar
  2. K.A. Abrahamson, R.G. Downey, and M.R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic, 73:235-276, 1995. Google Scholar
  3. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge, 2009. Google Scholar
  4. T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question. SIAM J. Comput., 4(4):431-442, 1975. Google Scholar
  5. Y. Chen and J. Flum. Machine characterizations of the classes of the W-hierarchy. Proceedings of the 17th International Workshop on Computer Science Logic, Lecture Notes in Computer Science, 2803:114-127, 2003. Google Scholar
  6. Y. Chen, J. Flum, and M. Grohe. Bounded nondeterminism and alternation in parameterized complexity theory. Proceedings of the 18th IEEE Conference on Computational Complexity, pages 13-29, 2003. Google Scholar
  7. Y. Chen, J. Flum, and M. Grohe. Machine-based methods in parameterized complexity theory. Theor. Comput. Sci., 339:167-199, 2005. Google Scholar
  8. R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer, Berlin, 1999. Google Scholar
  9. R.G. Downey and M.R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  10. J. Flum and M. Grohe. Fixed-parameter tractability, definability, and model checking. SIAM J. Comput., 31(1):113-145, 2001. Google Scholar
  11. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2006. Google Scholar
  12. L. Fortnow. A simple proof of Toda’s theorem. Theory of Computing, 5:135-140, 2009. Google Scholar
  13. J.A. Montoya and M. Müller. Parameterized random complexity. Theory. Comput. Syst., 52:221-270, 2013. Google Scholar
  14. C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  15. A. Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. Google Scholar
  16. A. Shen. IP = PSPACE: simplified proof. J. ACM, 39(4):878-880, 1992. Google Scholar
  17. S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact