All Questions
Tagged with complexity-theory satisfiability
35 questions with no upvoted or accepted answers
7
votes
0
answers
173
views
Any Natural Problems shown Easy by Reduction to Horn SAT?
To show that a problem is polynomial-time solvable, an often-successful technique is to reduce it to 2SAT (that is the problem of deciding satisfiability of CNF formulas with every clause containing ...
- 363
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
3
votes
0
answers
319
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,641
2
votes
0
answers
42
views
Satisfiability of a boolean formula with two occurrences of each variable with a special ordering
I am interested in the complexity of a special case of the boolean satisfiability problem:
We are given a boolean formula, consisting only of the logical operators $\land$ and $\lor$ (that can be ...
- 161
2
votes
0
answers
45
views
Problems with proof of NP-completness of SAT following Cooks original paper
I am currently in the process of trying to understand the original proof of NP-completeness of SAT given in the seminal paper by Cook [COOK71] and have struggled with a few of the details of the proof ...
- 121
2
votes
0
answers
33
views
Reductions from 3-SAT that won't work directly from SAT
Our prof talked about why it's good to know that 3-SAT is NP-complete because it's easier to craft reductions from it than from plain SAT.
However, all the examples we've seen (reduction to ...
- 21
2
votes
0
answers
48
views
Non-trivial reduction form SAT to $3$-SAT
Looking for any idea for reduction from $SAT \leq 3-SAT$ where $SAT$ is known to have $d$ variables at most in each clause. I am looking for a reduction in which the resulting formula will not depend ...
- 534
2
votes
0
answers
41
views
Under ETH: $\exists$ Problem unsolvable in $2^{o(n)}$ $\Leftrightarrow^?$ 3-SAT can be represented in linear bits
It is a popular open question if there is a problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH. I recommend reading that question first. That question states that, assuming the ETH ...
- 2,511
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
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
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
2
votes
0
answers
107
views
Why does the proof that #SAT is in IP stop after m rounds?
I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of ...
- 21
2
votes
0
answers
408
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 ...
- 530
1
vote
0
answers
24
views
Are there any SAT outside of $\mathsf{RP}$ variants that are solvable in quasipolynomial time?
It's possible to construct SAT problems that are solvable in quasipolynomial time, but they are also solvable in polylogarithmic space. Consider, for example, the following problem:
Let a set $S$ ...
- 2,041
1
vote
0
answers
159
views
Why weakening rule doesn't increase the size of resolution refutation?
I am studying the complexity of SAT resolution refutation. There is a useful tool named weakening rule
The weakening rule:
B -->B ∨ C
says that from a clause B we can derive the weaker clause B ∨ ...
- 399
1
vote
0
answers
69
views
Restricted Planar 3-SAT NP-hard
As we all know, 3-SAT is NP-hard.
Two of the less known results are that Planar 3-SAT is NP-hard and also a 'restricted' 3-SAT, where any literal appears in at most two clauses turns out to be NP-hard....
- 133
1
vote
0
answers
77
views
Can these variants of SAT/Tautology be actually pretty simple?
There are 8 (very similiar) languages I'd like to discuss here:
CNF SAT
DNF SAT
CNF No-SAT (Existence of a false assignment)
DNF No-SAT
CNF Tautology
DNF Tautology
CNF Contradiction
DNF Contradiction
...
- 142
1
vote
0
answers
151
views
Reduction between Parity-SAT and approximate counting
Consider two problems as defined here.
Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:
The number of satisfying assignments for $f(...
- 249
1
vote
0
answers
63
views
Different definitions of Exponential Time Hypothesis
I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it:
Statement 1
There exists no $2^{o(n)}$ algorithm for $3$-SAT, where $n$ is the number of variables.
Statement ...
- 2,992
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 ...
- 111
1
vote
0
answers
147
views
Correct implication for 3SAT from this theorem?
Theorem. Let none of the assignments of length $\log n$ make a set of unsatisfiable 2-clauses. Then formula is satisfiable.
$n$ is input length here.
Let we name an assignment that make the formula ...
- 2,041
1
vote
0
answers
76
views
How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?
In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq ...
- 259
0
votes
0
answers
17
views
Does $\mathsf{NC_1\subsetneq NC}$ imply $\mathsf{NP\neq coNP}$?
Any $\mathsf{NC}$ circuit could be presented in SAT form via Tseytin transform. This applies in the reverse too: an arbitrary SAT instance could encode any $\mathsf{NC}$ circuit.
Now, Frege proof ...
- 2,041
0
votes
0
answers
111
views
The parameterized complexity of Weighted-CNF-SAT parameterized by the number of clauses
What is the parameterized complexity of Weighted-CNF-SAT, when parameterized by the number of clauses?
Input: A CNF formula $\phi$ with $m$ clauses and $n$ variables, and an integer $k$.
Parameter: $m$...
- 31
0
votes
0
answers
69
views
if it were shown that every algorithm that solves SAT must have complexity Ω(n^(log n)) then P≠NP?
Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong?
I can't find a formal proof
0
votes
0
answers
17
views
Complexity Class of the Problem: Existence of Unsatisfying Interpretations in Boolean Formulas
What is the complexity class of the problem if there exist two different interpretations that do not satisfy a given Boolean formula? I believe the problem of existence of an interpretation that does ...
- 1
0
votes
1
answer
532
views
Complexity of a variant of #Positive-2-SAT
#Positive-2SAT is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable.
The ...
- 43
0
votes
0
answers
81
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
0
votes
0
answers
253
views
Polynomial Reduction from 3SAT
Given an undirected graph $G=(V,E)$ where $V$ is a set of vertices, and $E$ is a set of edges and
given a set $D$ where $D \subseteq V $ and $ \forall v \in V \setminus D \: \mid \: \exists w \in D : ...
- 1
0
votes
1
answer
52
views
Can you help me find some examples of 3co-SAT for 4 variables?
I've been studying the examples of 3co-SAT recently.
It's easy to find an example of one variable.
$(x_1\lor x_1\lor x_1)\land (\overline{x_1}\lor \overline{x_1}\lor \overline{x_1})$
Examples of 2 ...
- 317
0
votes
0
answers
95
views
I need to show that the problem is NP-complete
Double-SAT = {𝜓: 𝜓 has at least two satisfying truth assignments}. Hint: reduce from SAT. Start with a formula 𝜑 and modify it to get a formula 𝜓 so that 𝜑 is satisfibale if and only if 𝜓 has at ...
- 11
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
0
votes
0
answers
152
views
Consequences from a lower bound of SAT problem
I'm not sure how lower bounds affect the question to the P=NP problem.
I.e. :
Let a SAT instance with a size of n be transformed into an instance of a problem X with a size of n3.
If you find a ...
- 97
0
votes
0
answers
1k
views
Polynomial Time Reduction: Set Cover to CNF-SAT
How to prove that Set Cover can be polynomial-time reduced to CNF-SAT?
- 1
-2
votes
1
answer
591
views
Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility
Given a gate called Nand with the following truth table:
A | B | A Nand B
------------------
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
We can define ...
