Questions tagged [3-sat]
3SAT is a famous special case of the boolean satisfiability problem (SAT).
4
votes
0answers
64 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 ...
3
votes
0answers
57 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
35 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
40 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 ...
7
votes
1answer
398 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 ...
4
votes
1answer
56 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
80 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
33 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
57 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
84 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
26 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
38 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
47 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
166 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
414 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
31 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
$...
0
votes
0answers
44 views
Is my logic correct and is this a new reduction and algorithm from 3 SAT to clique?
Is my logic correct? If so, is this a new reduction and algorithm from 3 SAT to clique? I could only find one SAT to clique reduction; it wasn't this.
Definitions:
A clause group of a SAT instance ...
-1
votes
1answer
206 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
151 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
415 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
46 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
60 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
275 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
273 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
304 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
474 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
45 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
485 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
98 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
71 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\...
7
votes
1answer
434 views
Randomized algorithm for 3SAT
There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment ...
1
vote
1answer
1k views
3-SAT with 3 variable occurences
3-SAT with at most 3 occurences per variable is $\mathsf{NP}$-hard.
Now I'll try to solve it using these:
Theorem: SAT where all clauses have length 3 and variables occur 3 times, is satisfiable.
...
1
vote
1answer
102 views
Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?
Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable).
Output: unsatisfiable formula.
Restrictions:
Every clause contains exactly 3 variables.
Every clause differs ...
3
votes
1answer
793 views
Why does the reduction from 3SAT to IS work?
I was reading about the reduction from 3SAT (input: formula) to Independent set (input (graph, k)) in order to prove that the latter is in NP-Complete. The reduction i've seen follow the next steps:
...
1
vote
1answer
166 views
monotone min 3-sat polynomial algorithm?
I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:
given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables x1,…,xnx1,...
0
votes
2answers
212 views
monotone min-3-sat polynomial algorithm?
I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:
given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables $x_1,\...
1
vote
3answers
642 views
Is this possible to solve 3SAT in O(n^24) time and O(1) space?
Assume that n is the number variables of the given 3CNF formula (n≥3) and all clauses in the given 3CNF formula are different.
That means that for each clause, each literal can be either positive ...
1
vote
2answers
524 views
Prove “almost clique” is NP complete
Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique.
Consider the language:
$L=\{\langle G,t\rangle \mid \text{the ...
0
votes
1answer
51 views
4
votes
1answer
224 views
What is the whole picture of the NP-hardness proof of Super Mario Bros?
I am reading the NP-hardness proof of Super Mario Bros. in the paper "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta.
I can get ...
0
votes
0answers
59 views
Polynomials vs CNF forms and P=BPP
Given a $3\mathsf{SAT}$ form to decide satisfiability takes exponential time.
Any boolean function has an unique polynomial representation. So decide $3\mathsf{SAT}$ satisfiability reduces to whether ...
3
votes
1answer
4k views
Reduction 3SAT and CLIQUE
Hello everyone this is my first question ever and I apologize if I ask in the wrong manner causing this post to be either closed or deleted. I'm learning Reductions and my professor has asked us to ...
1
vote
0answers
224 views
Decision problem 3SAT and Bip[3-1]
Consider the decision problem Bip[3–1], define as follows:
Instance: $G = (S,T;E)$, bipartite graph, with $d_G(s) = 3$ for all $s \in S$.
Question: Does there exist $S' ⊆ S$ such that in $H = [S'∪T]...
0
votes
0answers
32 views
Proving NP-Complete Help [duplicate]
I am trying to prove that the problem of having a person at the minimum x number of intersections to be able to see each street is NP-Complete. I think that the street problem is very similar to the ...
1
vote
1answer
227 views
Expressing 3-SAT in first-order logic
i read that First-Order Logic is strong enough to formalise all of Set Theory and thereby virtually all of Mathematics. How would you express in First-Order Logic the theorem:
3SAT is NP-complete?
0
votes
2answers
2k views
AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?
Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm?
According to This Link and to ...
1
vote
1answer
195 views
How to choose between UC and PL when using the DPLL algorithm?
We know DPLL algorithm is backtracking + unit propagation + pure
literal rule.
I have an example. There is one example to solve following Satisfiability problem with DPLL. if assign of "0" to ...
1
vote
1answer
369 views
Small hard 3-SAT instances
I have read various references that for 3-SAT instances with large numbers of clauses, the optimal clause/variable ratio to generate 'difficult' instances is around 4.
However, I would like to know ...
0
votes
0answers
206 views
prove that the satisfiability problem with each clause containing at most 3 literals, denoted by ≤3SAT, is NP-complete
I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than ...
