Knowledge compilation languages as proof systems
Knowledge compilation languages as proof systems
复制标题
作为证明系统的知识编译语言
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Florent Capelli
中科院分区：
文献类型：
--
作者：
Florent Capelli
本文研究了多项式族中高于coNP的证明系统，特别是#SAT和MaxSAT的证明系统。我们首先解释Cook-Reckow证明系统的概念如何应用于这些问题，并展示如何在知识编译中扭曲现有语言，如DNNF，以便它们可以被视为#SAT和MaxSAT等问题的证明系统。
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.