A Proof Checking View of Parameterized Complexity

Citation:
2012
Issue Date:
2012-07-27
Full metadata record
Files in This Item:
Filename Description Size
1206.2436v2.pdfSubmitted Version213.7 kB
Adobe PDF
The PCP Theorem is one of the most stunning results in computational complexity theory, a culmination of a series of results regarding proof checking it exposes some deep structure of computational problems. As a surprising side-effect, it also gives strong non-approximability results. In this paper we initiate the study of proof checking within the scope of Parameterized Complexity. In particular we adapt and extend the PCP[n log log n, n log log n] result of Feige et al. to several parameterized classes, and discuss some corollaries.
Please use this identifier to cite or link to this item: