FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
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: