# Questions tagged [2-sat]

The tag has no usage guidance.

50 questions
Filter by
Sorted by
Tagged with
25 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 ...
• 11
1 vote
150 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 ...
• 11
69 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 ...
1 vote
14 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-...
• 2,296
1 vote
47 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$?
97 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 ...
• 133
169 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 ...
38 views

### Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
• 2,822
21 views

• 582
1 vote
143 views

• 1,381
1 vote
594 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 ...
783 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 ...
• 41
1 vote
91 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$...
272 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 ...
321 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 ...
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 ...
• 143
122 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. ...
• 111
761 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 <...
• 329
211 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 ...
• 1,601
257 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 ...
• 1,601