The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged

4

Your problem is known as Weighted-2-satisfiability, and is known to be NP-complete. The easiest way to see that is by reduction from Vertex Cover (exercise). Note that the link above is about whether there is a satisfying assignment having at most $k$ true variables. This is equivalent to your problem (exercise).


0

If you require a logically equivalent CNF formula, then that will give you a worst-case exponential size formula. If, however, equisatisfiability is enough, then you can use Tseitin encoding, which will give you a polynomial size formula. The trick is in adding new atoms for logical operators.


3

Given a CNF with $n$ variables and $m$ clauses, we denote by $A_i$ the set of truth assignments that do not satisfy clause $i$. Then the number of satisfiable assignments is $$2^n-\left|\bigcup_{i=1}^m A_i\right|.$$ Since each assignment makes at most one clause false, $A_i$ and $A_j$ are disjoint for $i\neq j$. Also note $|A_i|=2^{n-n_i}$ where $n_i$ is ...


0

The point of my exercise is to encode the path existence in CNF Well, a trivial way to do this is by reducing the problem to 2-SAT, following this set of rules: Assing a literal to every edge of your graph, for example first element in first row become $a$, second element in first row become $b$ etc. Put in OR relation the literal in the "start" position ...


2

do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations? $3-SAT$ is known to be solvable in time $O(1.321^n)$. Therefore, there is no instance that would force a $\Omega(2^...


2

As confirmed independently in another answer, 2P2N-3SAT is already NP-complete. Another name for the fragment you are interested in is (3, B$k$)-SAT where "B" stands for Balanced and indicates that there are the same number of positive and negative occurences of the variables, $k$ is the number of positive and the number of negative occurences, and the 3 ...


-1

it is known that the certificate for SAT consists in a binary distribution of the literals that satisfies the formula but the certificate for a TAUTOLOGY must necessarily contain ALL the distributions of the variables, which must ALL satisfy the formula, otherwise we could not ascertain in any way that it is a tautology. ... Is the reasoning ...


-1

Suppose $P=NP$ then there is polynomial certificate for TAUTOLOGY and it is still open. In the world $P \neq NP$ there is still a hope for $NP = coNP$ but unlikely. May be there exits a polynomial certificate for TAUTOLOGY that shows $NP = coNP$. you can see the proof of $NL = coNL$ by Immerman or Szelepcsenyi, it is like p and np but for space complexity. ...


Top 50 recent answers are included