Infeasibility of instance compression and succinct PCPs for NP (Q619903): Difference between revisions

A question by \textit{H. L. Bodlaender, R. G. Downey, M. R. Fellows} and \textit{D. Hermelin} [``On problems without polynomial kernels'', J. Comput. Syst. Sci. 75, No. 8, 423--434 (2009; Zbl 1192.68288)] asks if there is a polynomial-time computable function that, given a sequence of \(m\) Boolean formulae each of length at most \(n\), computes a formula of length bounded by a polynomial in \(n\) such that the computed formula is satisfiable if and only if at least one of the given formulae is satisfiable. This paper settles the question in the negative, under the assumption that the polynomial-time hierarchy does not collapse. A number of consequences of this result, the maybe most prominent of which concerns kernalizability of certain graph problems, are shown.