New answers tagged

0 votes

MSAT and IMSAT problems (restricted versions of SAT)

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 $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

Top 50 recent answers are included