Questions tagged [2-sat]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
Anuj's user avatar
  • 33
0 votes
1 answer
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 ...
Anuj's user avatar
  • 33
0 votes
1 answer
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 ...
Anuj's user avatar
  • 33
0 votes
2 answers
53 views

Finding a 2SAT instance that has a specific solution set

Is there a 2SAT instance of variables $(a,b,c,d,e,f,g)$ that has exactly the solution set $S=\{ (1,0,0,0,0,0,0),(0,1,0,0,0,0,0),(0,0,1,0,0,0,0),(1,1,0,1,0,0,0),(1,0,1,0,1,0,0),(0,1,1,0,0,1,0),(1,1,1,1,...
DrownedSuccess's user avatar
2 votes
1 answer
1k views

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable. 3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
Daniel Donnelly's user avatar
2 votes
1 answer
25 views

I'm trying solve a problem using different versions of SAT, how exactly does mixing SAT affect the hardness of the problem?

I'm trying to solve a problem which I can solve in 3SAT or as a mixed 2,3,4 SAT. I know how hard each of those categories are individually and know the derivations of their hardness individually. But ...
Würthi's user avatar
  • 141
1 vote
1 answer
84 views

Why do the 2-SAT techniques do not work for 3-SAT?

i just want to know why the techniques we use to solve the 2-SAT problems cannot be used to solve the 3-SAT problem. So the techniques that i know that help solve 2-sat are the naive on where you just ...
hellothere177's user avatar
0 votes
1 answer
32 views

reducing the word problem for dtm to sat / cnf-sat / 2-sat

word problem: given a language L through a deterministic turing machine, is the word w in the language L? the problem should be decidable, since if there is a deterministic turing machine i can simply ...
heythere's user avatar
1 vote
1 answer
372 views

Proof that 2-sat is P-hard?

i figured out this is what i want to know: in Cook's theorem it is shown that SAT is NP-hard. he shows it by showing that sat is at least as difficult like the word problem for nondet. Polynomial Time ...
heythere's user avatar
4 votes
1 answer
477 views

3-SAT with atmost 3 variables and variable occuring once per clause

I've stumbled across this problem on CSES https://cses.fi/345/task/E/ and was wondering is it somehow reducible to 2-SAT with given constraints? So, the problem states that you need to solve a 3-SAT ...
ZZT Production DIY and Gaming's user avatar
1 vote
0 answers
24 views

example of an NL-completeness reduction?

I'm looking for simple examples of nondeterministic log-space completeness reductions. In particular I seem unable to construct any nontrivial widget using 2-SAT clauses, which is known to be NL-...
Albert Hendriks's user avatar
1 vote
1 answer
64 views

Describe statement "Exactly k out of n variables should be true" in 2-SAT in time polynomial to n and k?

I have a list of $n$ variables, exactly $k$ of which should be true. Is it possible to encode this as a 2-SAT problem in time polynomial to $n$ and $k$?
DrownedSuccess's user avatar
3 votes
1 answer
145 views

Is 2-SAT over Linear Real Arithmetic in P or NP?

The general boolean satisfiability problem (SAT) is NP-complete, and thus can't be solved in polynomial time (assuming $P \neq NP$). But the special case of 2-SAT is in P, and can be solved in linear ...
user3558515's user avatar
3 votes
3 answers
785 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 ...
V. Prasad's user avatar
  • 103
0 votes
0 answers
60 views

Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
Turbo's user avatar
  • 2,881
2 votes
1 answer
48 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\...
lollab's user avatar
  • 23
0 votes
1 answer
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 ...
ashishmax31's user avatar
1 vote
1 answer
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 ...
user128041's user avatar
0 votes
1 answer
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 ...
DBrons's user avatar
  • 13
0 votes
2 answers
80 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 ...
J. Schmidt's user avatar
1 vote
1 answer
186 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 ...
Ari's user avatar
  • 1,611
0 votes
0 answers
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 ...
Christopher Miller's user avatar
1 vote
1 answer
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 ...
Sohan Biswas's user avatar
0 votes
1 answer
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 (...
user avatar
0 votes
0 answers
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' ...
nimdrak's user avatar
  • 11
2 votes
1 answer
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 ...
Martin Inf1n1ty's user avatar
1 vote
1 answer
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 ...
donkey's user avatar
  • 352
3 votes
1 answer
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: ...
Narek Bojikian's user avatar
3 votes
2 answers
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 ...
Asherydev's user avatar
1 vote
0 answers
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....
Sara Kat's user avatar
  • 111
3 votes
2 answers
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 ...
user2668676's user avatar
8 votes
1 answer
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 ...
SapereAude's user avatar
0 votes
0 answers
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 ...
Manoharsinh Rana's user avatar
1 vote
0 answers
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/...
Gregor K's user avatar
1 vote
1 answer
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–...
Rikard Olsson's user avatar
1 vote
0 answers
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 ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
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 ...
Mike Battaglia's user avatar
0 votes
1 answer
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 ...
Simin 's user avatar
  • 21
2 votes
0 answers
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 ...
Surfrider's user avatar
0 votes
1 answer
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 ...
student's user avatar
  • 19
1 vote
1 answer
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?
jørgen k. s.'s user avatar
1 vote
3 answers
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 ...
NedaHn's user avatar
  • 125
5 votes
1 answer
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, ...
younes zeboudj's user avatar
2 votes
1 answer
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 ...
rus9384's user avatar
  • 1,417
2 votes
1 answer
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. ...
rus9384's user avatar
  • 1,417
1 vote
1 answer
104 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: $\...
rus9384's user avatar
  • 1,417
1 vote
1 answer
633 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 ...
Farewell Stack Exchange's user avatar
4 votes
2 answers
929 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 ...
fragga's user avatar
  • 41
1 vote
1 answer
106 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$...
Revolucion for Monica's user avatar
2 votes
0 answers
347 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 ...
Manuel Lafond's user avatar