Knowledge compilation languages as proof systems

March 10, 2019 · The Ethereal · 🏛 International Conference on Theory and Applications of Satisfiability Testing

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Florent Capelli arXiv ID 1903.04039 Category cs.CC: Computational Complexity Cross-listed cs.AI Citations 13 Venue International Conference on Theory and Applications of Satisfiability Testing Last Checked 6 months ago
Abstract
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity