Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

13

$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness. Here is a polynomial algorithm. Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge c_2\cdots \wedge c_m$, where $c_i$ is the $i$-th clause. Output: true if $\phi$ becomes 1 under some assignment of all variables. Procedure: Construct set $B_i$...

11

A problem $P$ is NP-complete if: $P$ is NP-hard and $P \in \textbf{NP}$. The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction ...

9

If the truth value of a formula is determined by setting only a subset of the variables, an author might skip describing the remaining truth values. However, by definition, a truth assignment gives a value to every variable.

9

There is some research in this area. In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both satisfiable and unsatisfiable SAT instances. The theoretical justification for the speedup is that in CDCL solvers a restart allows the search to benefit from ...

7

Given a graph $G = (V,E)$, here is a SAT instance which is satisfiable iff the graph is not connected. Pick an arbitrary vertex $v_0 \in V$, and add the following clauses, over the variables $x_v$ for $v \in V$: $x_{v_0}$. For every $(u,v) \in E$, $\lnot x_u \lor x_v$ and $\lnot x_v \lor x_u$. $\bigvee_{v \neq v_0} \lnot x_v$. Here is a SAT instance which ...

6

I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, it's actually a $(1-2^{-k})$-approximation (Wikipedia cites this to Vazirani's book). Your suggestion is still only a $\tfrac12$-approximation in this case (...

6

Is there an official way to choose half of the clauses that satisfy the formula? There is no official way. As noted by Juho, "any algorithm that you prove correct is acceptable". Moreover, you do not have to choose that half of the clauses explicitly. Here is the simplest algorithm to decide $\text{HALF-2-SAT}$ that runs in polynomial time. In fact, it ...

5

The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps. What remains to be shown is that there is ...

5

The proof of the Cook-Levin theorem shows that for any nondeterministic Turing machine $M$, any input $x$, and any (reasonable) time bound $t(n)$, we can construct (efficiently) a SAT formula of size proportional to $t(|x|)^2$ that is satisfiable iff $M$ accepts $x$ within $t(|x|)$ steps. If you know that $M$ is supposed to halt within $t(n)$ steps, then ...

4

As I have mentioned in the comments, being able to determine the number of truth assignments of a generic formula in polynomial time would imply not only $\textbf{P} = \textbf{NP}$ but actually the much, much stronger $\textbf{#P} = \textbf{P}$ (see Yuval Filmus' answer). What Papadimitriou really means in this context is that the number of truth ...

4

The graph below is a positive answer without words. Here is the detailed proof. Definitions Let $X$ be an instance of X3SAT. $X$ is linear if any two clause shares at most one variable. $X$ is monotone if all literals in all clauses are positive. A walk in $X$ is a sequence of clauses where each clause is not disjoint with the clause following it. The ...

4

Your trick doesn't really work. There are several issues. First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$. But that doesn't tell you anything about the relationship between the number of unsatisfiable circuits of size $n$ vs the number of satisfiable circuits of size $n$. And, in ...

4

Your language consists of all valid encodings of a 2-CNF formula. Consider a random assignment to the variables of $\varphi$, i.e. each variable is assigned True/False with probability $\frac{1}{2}$, then the expected portion of satisfied clauses is $\frac{3}{4}$ (use linearity of expectation and note that each clause is not satisfied with probability $\frac{... 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). 4 Yes. You can solve this in polynomial time. The same strategy as in Are SAT problems with at most one false clause NP-complete? works. Let$\varphi$denote the CNF formula you care about, and$n$the number of variables in$\varphi$. Let$A_{i,j}$denote the number of truth assignments that do not satisfy clauses$i$or$j$of$\varphi$, let$A_i$denote ... 3 The sets of satisfiable and unsatisfiable formulas are the same size: both are countably infinite. However, that doesn't imply that there's any particular relationship between the number of satisfiable and unsatisfiable formulas of length$n$. For example, considering the natural numbers: There are countably many odd numbers and countably many even ... 3 For any fixed$k$, a$k$-CNF with at most four clauses has at most$4k$variables. So you can count the satisfying assigments with count = 0 j = number of variables for v1 = 0 to 1 do for v2 = 0 to 1 do ... for vj = 0 to 1 do if formula_value(phi, v1, ..., vj) == true count = count + 1 This runs in time$\...

3

Counting the number of satisfying assignments in known as #SAT, and is the canonical #P-complete problem. In particular, we don't expect it to be possible to count the number of satisfying assignments of a $k$-variable formula of size $m$ in much better than $O(2^km)$. In contrast, an $O(2^km)$ algorithm does exist – just try all possible assignments.

3

This looks like a typo in your source, and your derivation looks correct. So the corrected statement should be: $S \models S' \iff S \land \neg S'$ is unsatisfiable or $S \models S' \iff {\boldsymbol \neg} (S \land \neg S')$ is satisfiable

3

Any language $L$ in NP is decided by some nondeterministic Turing machine $M$. By Cook–Levin, the problem "Does $M$ accept input $x$?" can be decided by constructing a Boolean formula $\varphi_{M,x}$ that is satisfiable if, and only if, $M$ accepts $x$. Hence $L$ reduces to SAT, so SAT is NP-hard.

3

Suppose that you have a CNF formula $x$ with input size $n$, and that you can solve $\text{SAT}$ in $O(n^c)$ time for some constant $c$. We construct a new formula $y$. For each clause $l_i$ in $x$, with terms $v_{i,k}$, add a new variable $t_i$ and the CNF clauses $\bigwedge_i(\neg t_i \vee l_i)$ and $\bigwedge_{i,k} (t_i \vee \neg v_{i,k})$. Now this ...

3

Encodings like this are notoriously slippery, so (of course) please carefully verify any outputs in case I've made a mistake somewhere. Please assume that all unbound variables are universally quantified; i.e., I write $\bigvee_i\ p_{si}$ instead of $\forall s\ \bigvee_i\ p_{si}$. Defining the partitions First, define partition variables: $p_{si} = \text{... 3 Here is a translation of the answer how to prove 4-SAT CNF is NP-complete to the current situation. Suppose an instance of 4-SAT over variables$x_1,x_2,\cdots, x_m$is given as a boolean formula $$f=c_1\land c_2\land \cdots\land c_m,$$ where$c_i$is a disjunction that has exactly 4 literals for all$i$. Introduce a new variable$s$. Suppose$c_i=w\lor x \...

3

It seems that you're trying to prove that $\#\mathrm{3SAT}$ is in $\mathrm{NP}$. Since $\#\mathrm{3SAT}$ is $\mathrm{\#P}$-complete, and $\mathrm{\#P}$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $\#\mathrm{3SAT}\in\mathrm{NP}$. The error in your attempted proof is that your certificate doesn't have polynomial ...

3

QSAT with only 2 literals per clause was shown to be in P back in 1979. Since the $\Sigma_k$ and $\Pi_k$ versions of QSAT can be reduced to equisatisfiable problems with 3 literals per clause using only a slight modification the method used to transform a SAT instance to 3SAT (i.e. putting all the new variables in the innermost existential group), those ...

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 ...

3

Yuval describes the general approach. Let the binary representation of the two numbers be $n_1,\dots,n_k$ and $m_1,\dots,m_k$, where $n_1$ is the most significant bit. Introduce fresh new boolean variables $t_1,\dots,t_k$. The intention is that these will indicate the common prefix of $n,m$. In particular, add the following clauses: $t_{i+1} \implies ... 2 I understand that this problem is undecidable in general case, but I only care for some practical cases. This is impossible if the program contains complicated loops infinite loops loops that depend on the value of the input, e.g. for(int i = 0; i < input; ++i) ... For program where loops can be unfolded, you can construct such a formula using either ... 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 ... 2 OK so now I figured this out. The problem is$NP$-complete. We could simply verify an assignment by checking each gate as an equation. For solving SAT of boolean function A(x), simply construct a equation,$y=y\otimes\lnot A(x)\$ would suffice.

Only top voted, non community-wiki answers of a minimum length are eligible