# Questions tagged [2-sat]

The tag has no usage guidance.

57 questions
Filter by
Sorted by
Tagged with
58 views

### Complexity of this variant of $positive -⊕2SAT$?

This is like a follow up question from my previous post about complexity of $positive -⊕2SAT$. The problem positive $⊕2SAT$ is defined as a problem where we need to find the parity of the number of ...
48 views

### Complexity of this variant of $⊕2SAT$?

The problem $⊕2SAT$ is defined as a problem where we need to find the parity of the number of solutions of $2$-$CNF$ formulae and is known to be $\oplus P$ complete. I introduce the following variant ...
62 views

### Is there a way to make a implication graph of the following expression?

Is there a way to make implication graph of expression of form : $$((x_1 \lor x_2)\lor(x_3 \lor x_2))\land(x_3 \lor x_4)$$ I haven't been able to find any sort of text on this and the usual way to ...
53 views

26 views

### Doubt regarding the implications of a 2-SAT constraint

Consider an example 2-SAT instance with the constraint (x1​ ∨ x2)​. This CNF has these two implications: ¬x1​→x2​ and ¬x2​→x1​. "They actually mean, if x1​ is false then x2​ must be true, and if ...
1 vote
698 views

### Showing resolution algorithm for 2SAT is polynomial time

I don't quite understand why the resolution algorithm completes in polynomial time for 2SAT but not 3SAT. I'm looking at slide 42 of these slides for reference. It is clear that given two clauses of ...
54 views

### Algorithm for assigning items to one of two sets (2-CNF?)

I have a set of items (A, B, C, D, ...) which I want to assign to one of two sets (set1, set2). Trying all possible assignments ...
80 views

141 views

### 2SAT problem testcase does not have any strongly connected components

My task is to solve the 2SAT problem. I have read online that a good method to solve this problem would be to construct an implication graph, where each statement of the form ...
1 vote
80 views

### Polynomial time counter of solutions of 2SAT expression with pure literals

As per the title, is there any polynomial time algorithm to count the number of satisfying arguments for a 2SAT expression with pure literals? An even shallower case: Is there any such counter when ...
277 views

### Maximum number of positive literals in 2SAT

MAX 2SAT is NP complete. Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (... 221 views

### the correctness of 2-satisfiability problem algorithm by using implication graph

I learned finding a solution of 2-sat problem algorithm below. The point are below (1) when constructing the implication graph (2) finding there is no occurrence of a variable x and its negation x' ...
368 views

### MAX 2-SAT is polynomial time reducible to 2-SAT?

I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard. I have issue about this statement: MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks ...
1 vote
682 views

### Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable

Using 2SAT and implication graphs, how could I prove the following properties of implication graphs: Suppose there is a directed path between literals l1 and l2 in G_φ. Then there is also a directed ...
1k views

### Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
622 views

### How Tarjan algorithm work for the 2-SAT

Tarjan's algorithm for 2-SAT is based on the truth: a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation. But I ...
1 vote
780 views

### Min-Ones-2-SAT getting to vertex cover

In the Min-Ones-2-SAT problem, we are given a 2-CNF formula φ and an integer k, and the objective is to decide whether there exists a satisfying assignment for φ with at most k variables set to true....
2k views

### Give an NL-algorithm for complement of 2-SAT

Question1: What is the difference between 2SAT and the complement of 2SAT? 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 ...
687 views

### Is a "local" version of 3-SAT NP-hard?

Below is my simplification of part of a larger research project on spatial Bayesian networks: Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses ...
79 views

### 2-sat and vertex cover [duplicate]

I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of ...
1 vote
207 views

### Can someone give me the resolution procedure for 2 SAT, which is O (nˆ2)

According to Wikipedia, Even, S .; Itai, A .; Shamir, A. cited it in "On the complexity of time table and multi-commodity flow problems". The paper can be found here: http://www.cs.technion.ac.il/...
1 vote
206 views

### Counting models satisfying a boolean formula

I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–...
1 vote
32 views

### Proof that MAX-2-SAT is NP-hard [duplicate]

According to Wikipedia, while the 2SAT problem is polynomial, its maximization variant MAX2SAT is NP-hard. But, they do not provide a reference for this claim. Is this obvious? If not, where can I ...
43 views

### General structure of solutions to 3-SAT circuits

Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any ...
1k views

### 2SAT Problem using Implication Graph

I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each ...
72 views

### Reducing a problem to 2-SAT

Given a matrix $A$ with entries $a_{ij} \in \{0,1\}$, the matrix $B$ is formed by $b_{ij}=a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1}$. $B$ has one row and one column less than $A$. The problem is ...
71 views

### For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

For which $c, d$ is $Gap2SAT[c, d]$ in $P$ (such that $0<c<d<1$)? (I know if d=1 then for each c it will be in P, however with which c,d such that $0<c<d<1$ can I simply return ...
1 vote
43 views

### Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf?

I know that not all truthtables have a corresponding 2-cnf representation, but is there a way to find out if a given truthtable has a 2-cnf representation, and if so to find what that is?
1 vote
151 views

### NP-hardness of an extention of 2 sat

a 2 sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete k variables, also remove clauses contain them, in order to satisfy the 2-sat ...
728 views

### Even, Itai & Shamir's limited backtracking algorithm for 2-SAT: is it really linear?

I have read in Wikipedia (and other sources) about the limited backtracking algorithm of Even, Itai & Shamir for solving 2-SAT problem in a linear time, but the approach doesn't seem to be linear, ...
51 views

### 2CNF with 3 variable occurences

If we do not allow unit clauses, can 2CNF containing 3 occurences per variable be unsatisfiable? Every time I try to connect opposing variables to a cycle, I need to draw 4 edges for at least one ...
511 views

### Is this case of weighted 2SAT NP-complete?

Weighted 2SAT asks if it is possible to satisfy the formula with at most $k$ variables set as positive/negative. Trivially, every instance must be in 2CNF. It is known to be $\mathsf{NP}$-complete. ...
1 vote