Questions tagged [2-sat]
The 2-sat tag has no usage guidance.
33
questions
-1
votes
0answers
22 views
Logspace reduction from PATH to 2SAT
It is known that PATH (given a directed graph G and two vertices s,t is there a path in G from s to t), and 2SAT are NL-complete problems. Find a logspace reduction from PATH to 2SAT.
2
votes
1answer
57 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
64 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
456 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:
...
1
vote
1answer
79 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
108 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
215 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
422 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
66 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
146 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
104 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
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 ...
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 ...
0
votes
1answer
344 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
53 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
53 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
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
105 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
344 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
39 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
149 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
50 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
417 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
659 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
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$...
2
votes
0answers
205 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
209 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
877 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
110 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
680 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
183 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
202 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 ...
11
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: ...
