Knowledge compilation languages as proof systems
Type de document :
Pré-publication ou Document de travail
Titre :
Knowledge compilation languages as proof systems
Auteur(s) :
Capelli, Florent [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Discipline(s) HAL :
Informatique [cs]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Collections :
Source :
Fichiers
- http://arxiv.org/pdf/1903.04039
- Accès libre
- Accéder au document
- 1903.04039
- Accès libre
- Accéder au document