Questions tagged [3-sat]
3SAT is a famous special case of the boolean satisfiability problem (SAT).
112
questions
2
votes
1answer
170 views
Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset
I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
0
votes
0answers
21 views
Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]
Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems?
If 3-Sat takes exponential time, then could it be possible that ...
0
votes
0answers
19 views
What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?
What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?
Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?
1
vote
1answer
39 views
When does Gaussian elimination solve exact 1-in-3 SAT?
Terms:
A literal is a variable or its negation.
A clause is a set of literals.
An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 ...
1
vote
0answers
52 views
CircuitSAT to 1-in-3SAT
This question follows
Unique 3SAT to Unique 1-in-3SAT
Consider an AND gate such that (A ∧ B) = C. It can be trivially expressed in 3SAT with 4 clauses and no extra variables.
$$
(A ∨ B ∨ \overline{...
2
votes
2answers
148 views
Unique 3SAT to Unique 1-in-3SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.
It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such ...
1
vote
1answer
26 views
Unique 1-in-3 SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.
I know the value of each bit of the unique assignment because it was made from a binary ...
1
vote
1answer
136 views
How to prove finding two paths that are at least k edges apart is NP-hard?
Let $G=(V, E)$ be an unweighted, undirected, and connected graph. Given two start vertices $s_1$ and $s_2$ and two end vertices $t_1$ and $t_2$ is there a path from $s_1$ to $t_1$ and $s_2$ to $t_2$ ...
0
votes
0answers
24 views
How sub-exponential time does $\text{3SAT}$ have to be to make $\text{NP} \neq\text{EXP}$? What else would imply $\text{NP} \neq\text{EXP}$?
The exponential-time hypothesis posits that if $\mathsf{3SAT}$ has NO subexponential time algorithm (i.e. one in $\mathcal O(2^{o(n)})$), then $\mathsf{P}\neq \mathsf{NP}$.
However, I am interested ...
1
vote
1answer
20 views
For given reduction f, can show “if f(x) in 4NAE then x in 3SAT”, but not “if x is not in 3SAT then f(x) not in 4NAE”
Claim: $3SAT \le_p 4NAE $, where reduction $f$ is defined as such: given a 3CNF formula $\varphi$, add to each clause a new literal $z$ (where $z$ is same literal for each clause), and return new ...
10
votes
2answers
3k views
What is wrong with this simple proof of P=NP?
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiabilty problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
1
vote
1answer
69 views
Time complexities of state-of-the-art SAT solvers with respect to length of the formula
I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables.
If I am not mistaken, one of the reasons why most believe P does not ...
1
vote
1answer
67 views
Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts
The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,...
3
votes
1answer
36 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 ...
0
votes
0answers
24 views
Subset sum reduction to 3SAT [duplicate]
I have gone over numerous proofs that reduce 3SAT to Subset sum reduction and then claim equivalence, however the other direction is never coherently explained in these proofs. In particular the proof ...
7
votes
1answer
632 views
Random restarts for unsatisfiable instances
In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice.
...
1
vote
2answers
64 views
Change the structure from 3SAT to 1in3 3SAT
There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
1
vote
0answers
48 views
How does the number of clause affect the difficulty of a 3-SAT Problem? [closed]
It was asked here and closed although it is a very specific question witch was exactly answered in several papers. The complexity of 3-SAT problems has a phase transition which reaches the critical ...
0
votes
1answer
51 views
Descriptive complexity of 3SAT
lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity.
I found many formulas in $\exists$$SO$ that describe problems with graphs but none ...
2
votes
1answer
73 views
3-CNF to “independent form”
Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the ...
4
votes
0answers
96 views
What is the generating algorithm for the “komb” instances found on satcompetition.org?
For the 2017 and 2018 Random SAT Tracks of the SAT Competition ran by the International Conference on Theory and Applications of Satisfiability Testing there are small, yet difficult, random 3-SAT ...
2
votes
0answers
94 views
How many isomorphic 3SAT formulas?
For a 3SAT formula with $n$ variables and $m$ clauses, I am interested in counting the number of isomorphic formulas (isomorphic in the sense that they are logically equivalent and have the same ...
2
votes
1answer
59 views
3-SAT with negative-literals in each clause
Does a 3-SAT problem, where in each clause there is at least a negative-literal, always has a solution?
After looking at it, seems to me that the answer is yes, but maybe there is something I am not ...
2
votes
0answers
43 views
Is a “stacked”, “local” version of 3-SAT NP-hard?
In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard. My question below builds ...
8
votes
1answer
443 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 ...
5
votes
1answer
111 views
Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption
I want to prove that, assuming Exponential Time Hypothesis is true, there is no algorithm that solves Independent Set in $2^{o(|V|+|E|)}$ time. I want to apply the following strong parameterized many-...
2
votes
2answers
238 views
Proof that POSITIVE-3-SAT is in the complexity class P
I have the following language:
$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of ...
0
votes
1answer
71 views
Resolution when clauses contain more than 1 complementary literals
Let's assume that we have clauses $(l_1 \lor l_2 \lor l_3), (\neg l_1 \lor \neg l_2 \lor l_4), (l_1 \lor l_2 \lor l_5), (\neg l_1 \lor \neg l_2 \lor l_6)$, where both $l_1$ and $l_2$ are complementary ...
1
vote
0answers
142 views
The NP completeness proof for a variation of the 3CNF-SAT problem
There is a variation of 3CNF-SAT which is called 10-3-CNF-SAT = {<$\Phi$>: $\Phi$ is a satisfiable CNF formula with $\textbf{at most}$ 3 literals per clause and every variable occurs in $\textbf{at ...
3
votes
2answers
142 views
Is every X3SAT instance with no cycles satisfiable?
Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
0
votes
0answers
28 views
Reducing SAT to a P problem in polinomial time [duplicate]
Does reducing SAT in polynomial time to a P problem would mean that P = NP?
0
votes
1answer
67 views
Fine-grained complexity of 3-CNF formula evaluation
It's well known that 3-SAT is in NP, which means that one can evaluate a 3-CNF formula in polynomial time. However, I was wondering what the tightest upper bound is for formula verification, expressed ...
1
vote
1answer
56 views
Why not do these checks on the number of clauses in 3-SAT?
I've been writing a 3-SAT solver for fun and comparing its performance against the solver pycosat. My solver vastly outperforms pycosat in two special cases, where I solve by doing simple, obvious ...
3
votes
1answer
21 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 ...
0
votes
1answer
382 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 ...
1
vote
2answers
722 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 ...
0
votes
0answers
32 views
USAT, Arora Barak's book
Here on the page 354 Arora and Barak write below the shaded area
"but in fact $f(\phi)$ $\notin SAT$"
and not
"but in fact $f(\phi) \in SAT$"
While in the last line of the shaded area they write
$...
-1
votes
1answer
257 views
NP-completeness of vertex cover
Show that the following language is NP-complete
$$ L = \{ \langle G,k \rangle \mid \text{$G$ is a graph with a set $S$ of $k$ vertices hitting every edge of $G$}\}. $$
I know I should reduce the ...
1
vote
1answer
223 views
Assuming that P=NP - Finding an optimal algorithm for 3SAT
Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time.
Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of ...
1
vote
1answer
786 views
3-SAT reduction to jobs scheduling problem (np-completeness)
In this paper with the title of "NP-Complete Scheduling Problem" by J. D. Ullman, I am trying to understand the reduction from 3-SAT problem to a scheduling problem in order to prove the later is also ...
0
votes
0answers
52 views
3-SAT reduction to image matching problem
I have a research paper, Elastic image matching is NP-complete by Daniel Keysers and Walter Unger, that illustrates the reduction from 3-SAT to an image matching problem in order to prove that this ...
3
votes
0answers
68 views
Finding same-cost assignments for 3-SAT formulas
Suppose I have a 3-SAT formula in CNF with $ m $ clauses on $ n $ variables,
$$ F = C_1 \wedge \dotsb \wedge C_m, $$
with each clause $ C_i = l_{i_1} \vee l_{i_2} \vee l_{i_3} $ and each literal $ l_k ...
3
votes
1answer
387 views
Is integer factorization reducible to subset sum?
Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?
We assume that we know the algorithm solving the problem of Subset ...
1
vote
3answers
614 views
How many 3-SAT expressions with up to N variables are satisfiable?
TL;DR
There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
1
vote
1answer
523 views
Can I assume every clause of 3SAT has one positive literal?
Can we assume that each clause in 3SAT contains at least one positive literal? That is, there is no clause with all negative literals (but it is fine that there is a clause with all positive literals)....
0
votes
1answer
721 views
Show that maximum disjoint set problem is NP Complete
I have been thinking on this problem but couldn't come up with a good reduction yet. First part of the proof, i.e L is being in NP, is okay. However, I cannot find a proper reduction from 3-CNF-SAT to ...
3
votes
1answer
56 views
Could a modification of Krom's proof system be used to solve 3-SAT in polynomial time?
A literal is a nonzero integer, and we define $\sim x = -x$.
A clause is a nonempty set of literals.
A CNF is a set of clauses.
A K-rule is a pair $(F,C)$ where $F$ is a CNF and $C$ is a clause.
A ...
3
votes
3answers
692 views
How does the number of clauses affect the difficulty of a 3-SAT problem? [closed]
What is the relationship between the number of clauses and the difficulty of a 3-SAT problem?
1
vote
3answers
106 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 ...
1
vote
0answers
83 views
Is such variant of SAT always satisfiable?
Let we have a SAT instance where every clause has length $\ge3$ (when length $2$ is allowed, it can be unsatisfiable) and each pair of literals appear only once.
Non-example: $(x\lor y\lor z)\land(x\...
