Questions tagged [2-sat]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
2answers
48 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 ...
7
votes
1answer
398 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 ...
0
votes
0answers
59 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
1answer
43 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
0answers
126 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
1answer
64 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
0answers
20 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 ...
0
votes
1answer
169 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 ...
3
votes
1answer
21 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 ...
2
votes
0answers
49 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 ...
1
vote
1answer
34 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
3answers
98 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 ...
3
votes
1answer
243 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, ...
2
votes
1answer
31 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 ...
2
votes
1answer
122 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
1answer
36 views

How 2-QCNF algorithm works?

Suppose we have following 2-QCNF problem: $$\forall x_1...\forall x_m\exists y_1...\exists y_k:\varphi(x_1,...,y_k)$$ where $\varphi$ is 2-CNF. When the formula is false? Rules that I found: $\...
1
vote
1answer
339 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 ...
4
votes
2answers
574 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 ...
1
vote
1answer
82 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$...
2
votes
0answers
178 views

Is Max-2SAT with exactly 3 occurrences per variable APX-hard?

The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied. The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in at most 3 clauses (counting ...
3
votes
1answer
186 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 ...
4
votes
1answer
753 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 ...
0
votes
0answers
100 views

How to check wether a 2SAT implication graph has a bad loop or not?

m doing a practise quiz which my professor has posted online, one of the questions im very confused about was this one. ...
5
votes
2answers
624 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 <...
2
votes
1answer
166 views

Schaefer's dichotomy theorem and reformulating 3-literal clauses

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would ...
11
votes
3answers
1k 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: ...
3
votes
0answers
173 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 ...