Downloads provided by UsageCounts
handle: 2117/389909
Abstract MaxSAT, the optimization version of the well-known SAT problem, has attracted a lot of research interest in the past decade. Motivated by the many important applications and inspired by the success of modern SAT solvers, researchers have developed many MaxSAT solvers. Since most research is algorithmic, its significance is mostly evaluated empirically. In this paper, we want to address MaxSAT from the more formal point of view of proof complexity. With that aim, we start providing basic definitions and proving some basic results. Then we analyse the effect of adding split and virtual, two original inference rules, to MaxSAT resolution. We show that each addition makes the resulting proof system stronger, even when virtual is restricted to empty clauses ($0$-virtual). We also analyse the power of our proof systems in the particular case of SAT refutations. We show that our strongest system, ResSV, is equivalent to circular and dual rail with split. We also analyse empirically some known gadget-based reformulations. Our results seem to indicate that the advantage of these three seemingly different systems over general resolution comes mainly from their ability of augmenting the original formula with hypothetical inconsistencies, as captured in a very simple way by the virtual rule.
Complexity of proofs, Lògica informàtica, Algorismes, SAT refutations, Computer logic, MaxSAT solvers, SAT problem, Proof complexity, Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.), Algorithms, Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Complexity of proofs, Lògica informàtica, Algorismes, SAT refutations, Computer logic, MaxSAT solvers, SAT problem, Proof complexity, Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.), Algorithms, Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 65 | |
| downloads | 144 |

Views provided by UsageCounts
Downloads provided by UsageCounts