# Tag Info

## New answers tagged satisfiability

0 votes

For your first question, I'll give an elementary proof for the $\mathsf{NP}$-hardness of $\mathrm{MSAT}$ by reduction from $\mathrm{SAT}$. Let $\varphi$ be a propositional formula in CNF (i.e., a $\... • 1,311 0 votes ### Can you help me find some examples of 3co-SAT for 4 variables? CNF is only used to describe problem formally, but it's kind of hard for human to understand it. Entailment is such tool that used to write "readable" formula. You can use propositional ... • 93 2 votes Accepted ### CNF-SAT time complexity and input processing No. The meaning of "polynomial-time" is "polynomial in the length of an input". We can still search for an algorithm that is efficient on short inputs. For instance, suppose we ... • 141k 4 votes Accepted ### Complexity of the (Complete/Assign) 3-SAT problem? Let$C_1 \lor \cdots \lor C_m$be a 3CNF. We replace the clause$C_i = \ell_1 \lor \ell_2 \lor \ell_3$with the clause$C'_i = \ell_1^{(i)} \lor \ell_2^{(i)} \lor \ell_3^{(i)}\$, that is, with a clause ...
• 270k

Top 50 recent answers are included