Questions tagged [3-sat]
3SAT is a famous special case of the boolean satisfiability problem (SAT).
198 questions
0
votes
1
answer
45
views
Satisfiability to graph isomorphism reduction
$\text{GI} = \{\langle A, B \rangle∶ \text{ graph A is isomorphic to graph B} \}$
I want to reduce from, $\text{3SAT}\leq_p \text{GI}.$
I know how to reduce from GI to SAT: Whenever we see two ...
- 23
0
votes
0
answers
91
views
Is this reduction from Exact 1-in-3-SAT to Subset Sum using Horowitz and Sahni's algorithm known?
I'm exploring a reduction from Exact 1-in-3-SAT (x3SAT) to the Subset Sum problem that allows the use of the Horowitz and Sahni algorithm, achieving a time complexity of
$\mathcal{O^*}(2^{𝑛/2})$ for ...
- 2,511
-1
votes
0
answers
58
views
Find a solution to the 3-SAT problem by finding an invertible matrix
The 3-SAT (3-Satisfiability) problem is a specific version of the Boolean satisfiability problem, which is fundamental in theoretical computer science and logic. Here are the key features of the 3-SAT ...
- 1
-1
votes
1
answer
74
views
Turing machine $\textbf{M}$, which ran in polynomial time, with an oracle
My question is I required to prove that there exists a deterministic Turing machine $\textbf{M}$, which ran in polynomial time, with an oracle approach to the $\texttt{SAT}$ language, such that: Given ...
- 25
0
votes
1
answer
67
views
Is it possible there exists a reduction that satisfies conditions of reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}?$
I am following the Barak and Arora book. I have asked this question regarding reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}.$
Is it possible to show that there exists a reduction that satisfies ...
user172436
1
vote
1
answer
70
views
Reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$
I am following the Barak and Arora book, in circuit chapter, they use direct reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$ directly without any clue.
How to construct an explicit reduction ...
user172436
0
votes
0
answers
48
views
Encapsulated linear memory of Turing Machine
A function $f$ is said to be thinking in an encapsulated linear memory if:
$f(x)$ is a polynomial block (that is, there exists a polynomial $q$ so that $|f(x)|\leq q(|x|)$) for each input $x$.
...
- 25
1
vote
1
answer
43
views
Is Monotone Not-Exactly-1 3SAT solvable in polynomial time?
I'm studying different variants of the SAT problem, and I came across the Monotone Not-Exactly-1 3SAT problem.
Specifically, this problem involves determining whether a Boolean formula in CNF, where ...
4
votes
1
answer
1k
views
Why can't we prove SAT is NP complete just using the Tseytin Transformation?
The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine.
I am confused as to why just the Tseytin Transformation does not imply/prove ...
- 43
1
vote
1
answer
53
views
is 3-SAT ∈ NTIME(n^3)?
I'm struggling to understand the time complexity of 3-SAT using a non-deterministic Turing machine, as well as the relationship between NTIME and DTIME
For example, let's say we have 2 literals. My ...
- 13
2
votes
1
answer
30
views
Limited constant degree HamCycle
Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem.
In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges ...
- 505
6
votes
1
answer
1k
views
Why is 3-SAT used for proving NP-Completeness so often?
I was wondering why 3-SAT is often chosen as the candidate problem from which one reduces from to prove the NP-completeness of another algorithm. I've seen it justified in places such as K&T by
...
- 203
2
votes
1
answer
224
views
Tseitin formula on 2-connected graph
How can we prove that for $\\\\$ every $\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a ...
user167124
0
votes
1
answer
140
views
Resolution on weakening rule by derived clause
How to prove that every clause that is implied by the input formula (learned or not) can be derived using resolution with weakening rule:
$\frac{C}
{C \vee D}$
(A clause $C$ is implied by $F$ if for ...
user150715
0
votes
1
answer
336
views
How fast can we make generalized k-SAT?
Suppose a generalized version of k-SAT where the usual clauses
(disjunctions of literals) are generalized to arbitrary Boolean functions of k variables. (For example,
$(x \oplus (y \land z)), ((x \...
user150715
2
votes
2
answers
928
views
How to find a satisfying assignment in polynomial time without the use of randomness?
Assume that we are given a formula in 3-CNF such that at least 1% of
the complete assignments satisfy it.
My question is how to find a satisfying assignment in polynomial time without the use of
...
- 1
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
31
views
Computational Learning Problem: 3-DNF Reduction
I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R
d and Y = {0, 1}. Consider the
class of Binary classifiers given by intersection of ...
- 1
1
vote
1
answer
250
views
If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine
I found the proof of this theorem from https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf.
Here is the screenshot of the construction of probabilistic Turing machine RP.
The idea of ...
- 31
0
votes
2
answers
231
views
Constructing an SAT formula from a Clique graph
We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand.
From my knowledge when ...
- 11
0
votes
1
answer
248
views
3sat to clique reduction program
I am searching for a program to convert 3sat to clique problem.
I tried following links
https://www.geeksforgeeks.org/maximal-clique-problem-recursive-solution/
https://www.geeksforgeeks.org/find-all-...
- 1
0
votes
1
answer
206
views
System of equalities and inequalities is NP-hard using a reduction from 3COLORING
We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
- 25
1
vote
1
answer
63
views
Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
2
votes
0
answers
77
views
Modified DPLL for 3-SAT by reducing to 2-SAT
In Boolean Satisfiability of CNF formulae we have $k$-SAT where each clause has at most $k$ literals. It is well known that $k$-SAT is polynomial time reducible to $3$-SAT. It is also well known that $...
- 135
0
votes
1
answer
111
views
Complexity of this variant of 3-SAT?
This post introduces a new variant of 3-SAT called EQUAL-3-SAT, where the number of 3-Literal clause is equal to the number of variable.
Consider the 3-SAT problem where the formula is in conjunctive ...
- 43
2
votes
1
answer
391
views
Is checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?
I want to know if checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?
By 3-literal clause, I mean it can ...
- 43
0
votes
2
answers
215
views
Generate a minimum number of clauses in 3-CNF form that give a unique solution
Suppose I would like to generate n clauses, in 3-CNF form, that would give a unique solution for m variables (m<n).
Example: for m=6, I've got {a,b,c,d,e,f} = 111010
How to generate these n 3-CNF ...
0
votes
2
answers
194
views
Ιf 3SAT reduces to its complement then NP=coNP
Can you please explain to me why the following is true?
Ιf 3SAT reduces to its complement then NP=coNP.
Thoughts:
3SAT is NP-complete so for every X in NP
$X \leq 3SAT$
$\overline {3SAT} $ is NP-...
- 57
1
vote
1
answer
523
views
Variation of 3-SAT
I already know that SAT and 3-SAT are NP-complete.
If in 3-SAT the Boolean expression should be divided to clauses,such that every clause contains at most (in the original problem it says exactly) ...
- 57
1
vote
1
answer
155
views
How to reduce 3SAT to TwoOrMoreSAT?
I want to prove, that 2OrMoreSAT is NP-complete. It's defined as follows:
A formula is considered strongly satisfiable if there exists a model such that two or more different literals in every clause ...
- 11
-2
votes
1
answer
33
views
How to prove that it is NP-complete?
I was trying to do this exercise, but I don't know how to solve this problem is NP-complete, what reduction to do.
There is a network N of n people, in which every person i is associated with a subset ...
0
votes
1
answer
172
views
MAX-SAT approximation factor
I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm
MAX-3SAT:
set every variable with a random value ($0$ or $1$ each ...
- 3
3
votes
1
answer
196
views
NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable
For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause.
With the purpose of proving some ...
- 817
0
votes
1
answer
49
views
NP-hard (3-)SAT variant with $n$ clauses and $f(n)$ variables
With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ ...
- 817
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)....
- 548
2
votes
1
answer
30
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 ...
- 151
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
0
answers
59
views
Could we know what's the total number of unsatisfiable 3SAT formulas for a given n variables?
given some $n$ variables I would be interested to know what is the count of all 3SAT formulas under $n$ that are unsatisfiable.
An example of all 3SAT forumlas under $n=3$ is the following:
$$
( x \...
3
votes
0
answers
81
views
Are Barthel instances good to use as benchmark for "hard" instances of 3SAT?
I was wondering if, given an algorithm for 3SAT, testing it on Barthel instances would provide a general idea of how well it empirically performs on hard instances. What would other hard instances ...
- 151
2
votes
0
answers
36
views
Do non-linear dynamical systems have the potential to have an edge on other algorithms when it comes to computing NP-complete problems?
In a recent presentation, I've seen the difficulty of NP-complete/NP-hard problems attributed to the fact that they often have "long range" correlations, or at least they can be interpreted ...
- 151
1
vote
1
answer
120
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 ...
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
2
votes
2
answers
164
views
what does **input** mean for the $3SAT$ question? Is it the number of variables $n$ or the number of clauses $m$
We know that $3SAT \in NP$,
and the definition of $NP$ is as follows:
$NP$ is the class of languages that have polynomial time verifiers.
But I have a question:
what does input mean for the $3SAT$ ...
- 317
0
votes
0
answers
94
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
1
vote
1
answer
127
views
Enumerating through Turing Machines That Solve Same Problem
Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT ...
- 11
2
votes
1
answer
711
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 ...
- 21
2
votes
1
answer
75
views
Complexity of a restricted SAT problem
I am wondering about the complexity of the following SAT related problem:
Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties:
The intersection of any pair of ...
- 123
3
votes
1
answer
1k
views
4-SAT but two literals per clause must be true
I'm trying to show that a modified 4-SAT in which at least two literals per clause must be true is NP-complete. I'll call it $4_2$-SAT. I understand the reduction from 3-SAT to 4-SAT, and I know why $...
- 31
3
votes
1
answer
135
views
Find the flaw in the 3SAT solver algorithm
I consider decision version of 3SAT problem.
Main idea is to find congruent clauses and construct such maximum formula,
which satisfiability/truth table won't be changed.
In case of unsatisfiable ...
4
votes
1
answer
764
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 ...
