Tag Info

14

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

12

2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT. Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $$(x_1 \lor \overline{y}) \land (y \oplus x_2 \oplus z) \land (\overline{z} \lor x_3)$$ with $y$ and $z$ as new variables.

9

First set all literals $x$ to $1$ if they appear in a clause $0 \vee x$, and set $\bar x$ to $0$. If that requires you to set some $x$ to both $0$ and $1$, it's unsatisfiable. Iterate this until you don't have to set any more literals to $0$. If you get this far without finding out that the formula is unsatisfiable, remove all clauses that contain a $1$. Now ...

7

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. When $p = 1/2$, the situation is more complicated. Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move ...

7

Also a similar solution is to define Zero and One variables and add two extra clauses $\bar{zero} \vee \bar{zero}$ for value 0 and $one \vee one$ for value 1. After that we can follow the Krom's algorithm.

7

You haven't specified the arity of your XOR relations, but like in the usual SAT-to-3SAT reduction, you can always arrange that their arity be at most 3. Now you are in great position to apply Schaefer's dichotomy theorem, which will tell you whether your problem is in P or NP-complete (these are the only two options). If it turns out to be in P, the next ...

5

By Schaefer's dichotomy theorem, this is NP-complete. Consider the case where all clauses have 2 or 3 literals in them; then we can consider this as a constraint satisfaction problem over a set $\Gamma$ of relations of arity 3. In particular, the relations $R(x,y,z)$ are the following: $x \lor y$, $x \lor \neg y$, $\neg x \lor \neg y$, $x \oplus y \oplus z$...

5

Below you can find a (non-optimized) python implementation of the algorithm. First, I give some hints explaining why this implementation runs in linear time. These hints assume that you know what is roughly going on, and that you have read the code. The algorithm runs up to two threads at any given time. Initially only one thread is run. Whenever reaching a ...

5

You are asking why we can model the equation $a \lor b$ as two directed edges in a graph. The answer is that mathematics is a free country, and we are allowed to do whatever we want. The only restriction we have to obey is that whenever we claim a result, it must be accompanied by a valid proof. This representation is used in an algorithm that decides ...

4

You can express the predicate "$x = y$" using one occurrence of each polarity: $$(x \lor \lnot y) \land (\lnot x \lor y).$$ Consider now an instance of weighted 2SAT, in which each variable appears at most $M$ times. Duplicate each variable $M$ times, and enforce that all copies are the same using the gadget above. Replace each occurrence of each variable ...

4

The theory you are after is universal algebra. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s dichotomy theorem, which was recently extended to arbitrary alphabets. 3SAT has no polymorphisms. NAE-3SAT has only negation as a polymorphism. All other classes ...

4

Your question is likely answered by Schaefer's dichotomy theorem. In particular, if an instance of your problem is a conjunction of formulas, each one depending on a bounded number of variables, then according to the theorem your problem is either in P or NP-complete; and moreover there is a simple criterion to decide which case it is.

4

The first step in implementing an algorithm is understanding why it works. In your case, Krom's algorithm is based on repeated application of the resolution rule $$\begin{array}{c} a \lor b \qquad \bar{a} \lor c \\\hline b \lor c \end{array}$$ Here $a,b,c$ are literals. This rule is valid, and applied to two 2-clauses produces a 2-clause. Hence there is ...

3

I think there is some confusion here. MAX-2-SAT is NP-Hard (and its decision version is NP-Complete), while 2-SAT is in P and hence also in NP. This means that 2-SAT is polynomial-time reducible to (the decision version of) MAX-2-SAT. The converse is not true unless P=NP. Let $\phi$ be a 2-SAT formula with $m$ clauses. If you really want to reduce an ...

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 Question1: What is the difference between 2SAT and the complement of 2SAT? The set of all strings that do not describe satisfiable 2CNF formulas. Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space? We don't know anything significant beyond that$\mathrm{NL}\...

3

Schaefer's dichotomy theorem doesn't purport to claim anything about what transformations might be possible / not possible. However, as Yuval says, we don't need Schaefer's theorem. We already know that 3SAT is NP-complete. Therefore, we know that if there is a polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT ...

3

This answer assumes that a 2CNF representation of a function is a 2CNF (on the same set of variables) that agrees with the function on all inputs. Let's say that a clause $C$ is consistent with a function $f$ if $\lnot C \Rightarrow \lnot f$. Let $C_1,\ldots,C_m$ be the collection of 2-clauses consistent with your function $f$. Then $f$ has a 2CNF ...

2

Aspvall, Plass and Tarjan describe a linear time algorithm determining the truth value of quantified 2CNFs in their paper A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Their algorithm is an extension of the well-known algorithm for solving 2SAT using directed reachability; their initial step is computing the strongly ...

2

The following is unsatisfiable: $$(x \lor y) \land (x \lor \lnot y) \land (\lnot x \lor z) \land (\lnot z \lor w) \land (\lnot z \lor \lnot w) \land (y \lor w).$$ This contains every variable exactly three times, not all of them of the same polarity. If you allow variables to appear less than three times, you can drop the last clause $y \lor w$.

2

This problem is NP-hard (and in addition hard to approximate and W[1]-hard), because maximum independent set can be reduced to it. Reduction: Each variable represents a vertex and each clause represents an edge.

2

The arrows symbolize material implication, which is the operator with the truth table $$\begin{matrix} A & B & A\Rightarrow B \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}$$

2

Assuming that P≠NL, we know that P-complete problems are not in NL. The prototypical example is the Circuit Evaluation Problem, in which you are given a circuit (with constants as inputs), and the goal is to determine whether it evaluates to true. Wikipedia describes many other P-complete problems. Some problems are not (known to be) P-complete, yet we ...

1

Here is a proof sketch. We will show that the given formula is unsatisfiable iff there exists a cycle containing both $x$ and $\lnot x$, for some variable $x$. Suppose first that there exists a cycle containing both $x$ and $\lnot x$. The existence of a path $x \to^* y$ in the implication graph means that in a satisfying assignment, if $x$ holds then so ...

1

You can reduce from independent set. Given a graph, have a variable for each vertex, and for each edge, add the four clauses $$x \lor y, x \lor \lnot y, \lnot x \lor y, \lnot x \lor \lnot y,$$ where $x,y$ are the variables corresponding to the vertices connected by the edge. I'll let you complete the proof.

1

The problem is that when you split your clauses, you don't transform your $4SAT$ problem to a $2SAT$ problem. You still have an $NP$-complete problem to which an efficient $2SAT$-algorithm cannot be applied. You need to prove separately that your new problem is in $P$.

1

You already have a description of how the graph is built from the formula. Think about a possible algorithm for doing the job. For example, you first scan over all variables in the formula, and you add two vertices into your graph for each. Now you only need to add in the edges into the graph. You can scan over the clauses, and if you see either form you ...

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