Questions tagged [2-sat]
The 2-sat tag has no usage guidance.
44
questions
0
votes
1answer
60 views
Why can $2$-SAT be solvable efficiently, but $3$-SAT not?
I am aware that 2SAT is polynomial while 3SAT is not, but I am looking for an intuition why its so. After all, even in 2SAT we can attempt all possible truth functions and its $2^n$. So I am hoping ...
0
votes
0answers
34 views
Is there a reduction from 2sat to bpm?
Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
2
votes
1answer
17 views
Padding a 2SAT clause
In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\...
0
votes
1answer
24 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
1answer
180 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 ...
0
votes
1answer
37 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 ...
0
votes
2answers
59 views
Are different assignments allowed for the implication graph proof of 2-SAT being in P?
One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor ...
1
vote
1answer
118 views
Complexity of specific cases of MAX2SAT
I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages
$L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT ...
1
vote
0answers
76 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
1answer
35 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 ...
0
votes
1answer
89 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 (...
0
votes
0answers
57 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' ...
2
votes
1answer
111 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
1answer
301 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 ...
3
votes
1answer
738 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:
...
3
votes
2answers
301 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
0answers
356 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....
3
votes
2answers
1k 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 ...
8
votes
1answer
540 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
74 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
0answers
156 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
156 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
26 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 ...
3
votes
1answer
27 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 ...
0
votes
1answer
633 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 ...
2
votes
0answers
56 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 ...
0
votes
1answer
69 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
1answer
36 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
128 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 ...
4
votes
1answer
513 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
46 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
248 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
71 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
565 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
754 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
88 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
259 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
282 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
1k 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
117 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
737 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
203 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 ...
3
votes
0answers
230 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 ...
14
votes
3answers
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: ...
