Relativization and interactive proof systems in parameterized complexity theory

DOI10.4230/LIPICS.IPEC.2017.9zbMATH Open1443.68070arXiv1706.09391MaRDI QIDQ5111868FDOQ5111868

Authors: Ralph Bottesch 

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1706.09391

Recommendations

• scientific article; zbMATH DE number 7378390
• Machine-based methods in parameterized complexity theory
• Some definitorial suggestions for parameterized proof complexity
• Parameterized proof complexity
• Computation Models for Parameterized Complexity

zbMATH Keywords

parameterized complexityinteractive proof systemsrelativization

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Computational Complexity
• Parametrized complexity theory.
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• PP is as Hard as the Polynomial-Time Hierarchy
• Title not available (Why is that?)
• IP = PSPACE
• Machine-based methods in parameterized complexity theory
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• IP = SPACE
• Fixed-parameter tractability, definability, and model-checking
• Computer Science Logic
• Parameterized random complexity
• A simple proof of Toda's theorem

Cited In (6)

• Some definitorial suggestions for parameterized proof complexity
• Parameterised counting in logspace
• Title not available (Why is that?)
• Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
• Title not available (Why is that?)
• Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs

This page was built for publication: Relativization and interactive proof systems in parameterized complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111868)