All Questions
Tagged with complexity-theory satisfiability
267 questions
-1
votes
1
answer
106
views
Equivalence of Horn formulas tractable?
Assume I have two Horn formulas $\phi_1, \phi_2$. Horn formulas are CNF formulas so that each clause has at most one unnegated literal. For example:
$x_1 \wedge (\neg x_1 \vee \neg x_2 \vee x_3 )\...
D.W.♦
- 166k
2
votes
0
answers
661
views
Reducing Dominant Set Problem to SAT
I am trying to solve a problem and I am really struggling, I would appreciate any help.
Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
- 53
-2
votes
1
answer
41
views
Does 2SAT contained in SAT?
Is it true that $2 S A T \subseteq S A T ?$ and in general is $k S A T \subseteq S A T $ where k is any positive integer is true?
Thanks.
- 11.7k
3
votes
1
answer
67
views
Reference asking: phase transition in SAT
This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate.
It has been experimentally observed (e.g. here) that when ...
- 279k
4
votes
1
answer
20k
views
Reduction of 3-SAT to Vertex Cover?
Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$?
I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of ...
- 21
3
votes
1
answer
353
views
Having trouble understanding a proof of Mahaney’s theorem
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.
I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $...
- 279k
3
votes
1
answer
639
views
Special Monotone SAT problem: NP complete?
Say we have the set $X=\{ x_1, x_2, \dots \}$ of variables. Then we consider the following problem: Is the formula
$$\bigwedge_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge_{(a,b,c) \in B}(\neg a ...
D.W.♦
- 166k
1
vote
2
answers
5k
views
How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?
I am studying for NP problems.
To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
- 11
2
votes
0
answers
89
views
Class of languages recognizable by n-bit formulas of size at most $T(n)$
A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-...
- 221
15
votes
2
answers
2k
views
MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?
What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard?
To formalize this more precisely, let
$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{...
CommunityBot
- 1
3
votes
1
answer
208
views
CNF satisfiability with a bound on number of clauses
Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness ...
- 2,241
4
votes
2
answers
382
views
Are SAT problems with at most two false clauses NP-complete?
Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), ...
D.W.♦
- 166k
3
votes
1
answer
136
views
High-dimensional geometry and P vs. NP
Background: Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered ...
- 1,000
1
vote
1
answer
302
views
Find a truth assignment of 2SAT that has the most number of true variables?
Given a 2SAT instance in CNF where each clause has at most two literals. Let $m$ be the number of clauses and $n$ be the number of variables et let $k$ be a positive number.
Question: Is there a ...
- 279k
5
votes
1
answer
678
views
Are SAT problems with at most one false clause NP-complete?
Is the problem of deciding whether a SAT instance, where at most one clause is false (that is, any given variable assignment will either lead to all clauses being true, or all but one), is satisfiable ...
CommunityBot
- 1
6
votes
2
answers
2k
views
Is the $k$P$k$N-3SAT problem NP-complete?
Consider the following 3-SAT variant defined over the variables $x_1,\ldots,x_n$. In the $k$P$k$N-3SAT problem each variable $x_j$, $j \in [n]$, occurs exactly $k$ times as a positive literal in $\phi$...
- 131
0
votes
1
answer
158
views
A doubt on converting NOT gate to CNF formula
For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.
My ...
CommunityBot
- 1
1
vote
1
answer
720
views
Is properly quantified 3SAT complete for PSPACE and all PH levels?
I know 3SAT is NP-complete and QSAT is PSPACE-complete. However, is it true that
$$\exists X_1 \forall X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$
is complete for $\Sigma_k$, the ...
- 8,149
31
votes
3
answers
1k
views
Measuring the difficulty of SAT instances
Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance.
One way is to run existing solvers, but that kind of defeats the purpose of estimating ...
CommunityBot
- 1
4
votes
3
answers
1k
views
Showing that HALF-2-SAT is in P
I need to show that the following problem is in P:
$$\begin{align*}\text{HALF-2-SAT} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and there exists an assignment} \\
&...
- 279k
2
votes
1
answer
86
views
Satisfiability Toward A Sequential Circuit
Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean ...
- 271
0
votes
1
answer
83
views
n-DNF boolean formula k satisfiability
Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n).
Where input is infinite number of n tuples where ...
- 8,149
8
votes
2
answers
3k
views
Is "Reachable Object" really an NP-complete problem?
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. ...
- 8,342
1
vote
2
answers
603
views
Why is Max SAT in P if SAT in P?
It holds that if SAT could be solved in poly time, one can also find in poly time the assignment that satisfies most clauses of the original formula.
Does anyone have any idea how to show this?
Let's ...
- 146
0
votes
1
answer
200
views
Can someone give me the definition of #Monotone-2SAT?
In the decision problem, I set all variables to true and see if the formula is satisfiable.
My question is because I do not understand how there can be multiple solutions, though all variables are ...
- 82.2k
0
votes
2
answers
149
views
Why is Boolean satisfiability such a rare case?
In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot ...
- 82.2k
1
vote
1
answer
224
views
Why Cook-Levin thorem's proof can mean SAT's NP-Hardness
I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ ...
- 82.2k
1
vote
0
answers
203
views
Could you show the intractibility of SAT by showing that the number of variables contributing to an arbitrary unsatisfied clause is not constant? [closed]
Preface: This is not an attempted proof at P vs NP
Starting with some CNF Boolean expression ϕ, by the rules of logical disjunction, a clause is only unsatisfied if each of the literals in it are ...
- 111
3
votes
0
answers
296
views
relationship between SAT and Min-ones SAT
If SAT can be decided in polynomial time, is it clear that Min-ones SAT can be decided in polynomial time? The idea I had was to take a poly decider of SAT and try it on a formula OR'd with all ...
- 181
6
votes
2
answers
3k
views
Reducing Zero-One Integer Linear Programming problem to SAT
I want to find a reduction from Zero-One Integer Linear Programming problem to Boolean Satisfiability problem (SAT), that is, to find a polynomial-time transformation $T$, such that:
$$IP \leq_P SAT$$
...
- 752
1
vote
1
answer
1k
views
Reducing 3SAT to MAX-3SAT
I have the following problem:
Consider the MAX-3-SAT problem: given a Boolean function in
Conjunctive Normal Form (CNF) determine the maximum number of clauses
that can be satisfied. Prove that ...
- 5,037
1
vote
0
answers
409
views
Is the solution to Independent Set or Vertex Cover from 3-SAT optimum?
There are plenty of resources online discussing 3-SAT reductions to Independent Set or Vertex Cover problem. I am unable to find a resource which states that a satisfiable assignment to 3-SAT results ...
- 241
1
vote
0
answers
96
views
3-SAT wher each literal appears at most once [duplicate]
I'm currently following a course and we have to prove that a restricted version of the 3-SAT decision problem where each literal appears at most once is solveable in polynomial time.
I think such a ...
- 187
2
votes
1
answer
187
views
Can QBF encode #QBF?
In another question Initializing non-deterministic variables in QBF, I was interested about translating assertion-based pseudocode to QBF in order to have an exponentially more compact encoding ...
- 101
3
votes
1
answer
491
views
In SAT, do we require an assignment for arbitrary variables?
I am reading about the Satisfiability Problem, in page (5) the author gives the following example :
$(P \lor Q \lor R) \wedge
(\bar{P} \lor Q \lor \bar{R}) \wedge
(P \lor \bar{Q} \lor S) \wedge
(\bar{...
- 22.8k
3
votes
3
answers
10k
views
Why is SAT in NP?
I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?
0
votes
1
answer
2k
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,459
3
votes
1
answer
9k
views
Drawing an implication graph for 2-SAT clauses
I am trying to convert the following 2-sat clauses to implications and then draw the implication graph.
The clauses are: ...
- 21
2
votes
1
answer
336
views
How to reduce MaxUNSAT to MaxSAT?
Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ?
When considering the MaxSAT problem, one often considers also the MinUNSAT problem, which is ...
CommunityBot
- 1
3
votes
1
answer
3k
views
SAT for positive CNF clauses with exactly half of the variables being true
I am focusing here on positive even SAT problems, that is a CNF for which all literals are positive, and in which an even number n of variables occur. This is obviously trivial : just set all ...
- 8,149
0
votes
0
answers
186
views
Proof of the Cook-Levin Theorem - snapshot transitions
I'm trying to understand the proof of the Cook-Levin thereom in Aurora and Barak's "Computational Complexity" text.
A snapshot $z_i$ of $M$’s execution on some input $y$ at a particular step $i$ is ...
- 597
1
vote
1
answer
248
views
P=NP giving a deterministic algorithm for SAT
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying assignment ...
CommunityBot
- 1
1
vote
2
answers
2k
views
What are known 3SAT to 2SAT reductions?
Is there a way to convert a 3SAT formula into a equisatisfiable 2SAT formula? Each method is of interest, even those that grow exponentially.
(So if, for example, my 3SAT formula has 16 variables and ...
- 8,149
3
votes
1
answer
2k
views
Reduce Max-Cut to Max-2SAT
I would like to find a reduction from Max-Cut to Max-2Sat.
Could someone shed light on this problem, preferably spiced with some intuition?
Thanks,
Matan.
- 279k
5
votes
2
answers
846
views
Hardness of mixed 3-SAT and 2-SAT formula
It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals.
We can solve this ...
- 8,149
7
votes
2
answers
2k
views
3-SAT where variables occur equally many times as a positive literal and as a negative literal
Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$.
Is it NP-...
- 103
1
vote
1
answer
1k
views
What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?
Definitions:
positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula.
negative CNF is a conjunctive normal ...
- 8,149
2
votes
1
answer
1k
views
Variant of 3-SAT is NP complete?
Consider a restriction on 3-SAT in which no literal occurs in more than two clauses.
How do we show that this is NP complete ?
(edit - I was getting confused over the definition on the 3-SAT,here by ...
- 56
2
votes
0
answers
30
views
Inapproximability result for a special version of 1-in-kSAT
Max 1-in-kSAT is the following maximisation problem :
Given $n$ variables $x_1,\dots,x_n$, and $m$ clauses $C_1, \dots, C_m$, find a valuation such that the number of clauses satisfied by exactly one ...
- 366
3
votes
0
answers
183
views
How hard is APPROXIMATE-#SAT? [closed]
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
- 31