Proof systems for #SAT based on restricted circuits
Author: Florent Capelli
Paper Information
Title: | Proof systems for #SAT based on restricted circuits |
Authors: | Florent Capelli |
Proceedings: | PC Abstracts |
Editors: | Jan Johannsen and Olaf Beyersdorff |
Keywords: | proof complexity, propositional model counting, knowledge compilation |
Abstract: | ABSTRACT. In this work, we extend a well-known connection between linear resolution refutation and read-once branching program by constructing proof systems based on syntactically restricted circuits studied in the field of Knowledge Compilation. While our approach only yield proof systems that are weaker than resolution, they may be used to define proof systems for problems such as #SAT or MaxSAT. This is a work in progress. |
Pages: | 2 |
Talk: | Jul 07 17:40 (Session 31M) |
Paper: |