MaxSAT (Boolean Satisfiability)

Description

Given an instance of SAT represented in Conjunctive Normal Form (CNF), compute an assignment to the variables that maximizes the number of satisfied clauses.

Related Problems

Generalizations: Conjunctive Normal Form SAT

Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-SAT, 2SAT, 3SAT, 3SAT-5, 4SAT, Monotone 3SAT, XOR-SAT, Horn SAT, Dual-Horn SAT, Renamable Horn

Parameters

$n$: number of variables

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
st-Maximum Flow	assume: SETH then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$	2018	https://dl.acm.org/doi/abs/10.1145/3212510	link
All-Pairs Maximum Flow	assume: SETH then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$	2018	https://dl.acm.org/doi/abs/10.1145/3212510	link
All-Pairs Maximum Flow	assume: SETH then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$	2018	https://dl.acm.org/doi/abs/10.1145/3212510	link
st-Maximum Flow	assume: SETH then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$	2018	https://dl.acm.org/doi/abs/10.1145/3212510	link
Maximum Local Edge Connectivity	assume: SETH then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$	2018	https://dl.acm.org/doi/abs/10.1145/3212510	link