# Questions tagged [2-sat]

The tag has no usage guidance.

41 questions
Filter by
Sorted by
Tagged with
2k views

### Is 2-SAT with XOR-relations NP-complete?

I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination? Example Input: 2-SAT part: ...
466 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 ...
706 views

### Can you solve 2-sat problem when truth assignments of some variables are determined

I am trying to find a assignment to satisfy a 2-sat statement. Problem is some of the clauses are 0 or x or 1 or x. I think the <...
693 views

### 2-SAT implication Understanding

Having a simple 2-SAT problem where the equation is simply: $a \lor b$ We have two implications: $\lnot a \Rightarrow b$ $\lnot b \Rightarrow a$ Thus, in the graph we build we add edges similar to ...
964 views

### How to do last step of Krom's algorithm for solving 2SAT problems

I was making a program for solving 2 SAT problems, using Krom's algorithm. I did not found a lot of information searching in Google, so I used Wikipedia's description of Krom's algorithm to implement ...
578 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: ...
425 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 ...
416 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, ...
23 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 ...
240 views

### Is SAT-Problem with XOR and AND NP-complete

Is this problem NP-complete? I have many restrictions like this and want to find a feasible solution: ((a and b) xor (c and d)) = 1 with a,b,c,d are arbitrary literals. It looks similar to XOR-2SAT ...
215 views

### “Balancing” positive and negative literals in 2-sat

I saw in an answer to this post that it is possible to construct 3-sat clauses with extra variables such that the number of positive and negative literals for each variable are equal. Does anyone ...
89 views

28 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 ...
113 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 ...
482 views

### Is this possible to solve 4SAT in polynomial time? [closed]

I know and admit that this is long, but please read it slow and understand everything. I think that this is one of the most interesting questions asked in computer science ever. I don't expect for ...
84 views

### 2-clause satisfiability associated graph

A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P: 2-SAT: Input : A conjunction $\Phi$...
47 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 ...
147 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 ...
167 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....
151 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/...
23 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 ...
107 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 ...
35 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 (...
46 views