Knowledge compilation languages as proof systems
This work addresses theoretical computer scientists by providing a framework for proof systems in complex computational problems, but it appears incremental as it builds on existing knowledge compilation techniques.
The paper tackles the problem of extending Cook-Reckhow proof systems to higher polynomial hierarchy problems like #SAT and maxSAT by adapting knowledge compilation languages such as decision DNNF, showing how these languages can be repurposed as proof systems for these problems.
In this paper, we study proof systems in the sense of Cook-Reckhow for problems that are higher in the polynomial hierarchy than coNP, in particular, #SAT and maxSAT. We start by explaining how the notion of Cook-Reckhow proof systems can be apply to these problems and show how one can twist existing languages in knowledge compilation such as decision DNNF so that they can be seen as proof systems for problems such as #SAT and maxSAT.