All Questions
Tagged with complexity-theory satisfiability
267 questions
0
votes
1
answer
102
views
Negating a Quantified Boolean Formula (QBF)
I'm reading about quantified boolean formulas. One sentence mentions:
You should also verify that the negation of the formula $Q_1x_1\cdot\cdot\cdot Q_nx_n \phi(x_1, ..., x_n)$ is the same as $Q^{\...
CommunityBot
- 1
0
votes
1
answer
73
views
Proving TWO-COLORED-HAMILTONIAN-CYCLE is complete
Consider the following problems:
TCHC :=
{
⟨G, c⟩ | G(V, E) is a directed graph with an even number of vertices along with
an edge coloring c and G has a directed Hamiltonian cycle with no
two ...
- 17k
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 ...
CommunityBot
- 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 ...
CommunityBot
- 1
0
votes
1
answer
54
views
Can we use XOR's forced branching to show that NP!=P
Backstory: As happens, every now and then, one encounters an idea, prompting the question: Could I use this to prove that NP==P, or vice versa NP!=P
So then, today I got to trying to show that NP!=P ...
D.W.♦
- 166k
17
votes
3
answers
10k
views
Prove NP-completeness of deciding satisfiability of monotone boolean formula
I am trying to solve this problem and I am really struggling.
A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,
$\qquad (x_1 \lor x_2) ...
4
votes
2
answers
1k
views
Practical hard 3-sat instances
The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (...
- 153
2
votes
1
answer
84
views
1-in-k-SAT problem restricted to only positive literals and at most two occurrences of a variable
1-in-k-SAT problem is to determine if there’s an assignment to variables such that every clause has exactly one true literal.
Is this problem known to be in P when restricted to positive literals, and ...
- 7,604
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 ...
D.W.♦
- 166k
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 ...
D.W.♦
- 166k
1
vote
1
answer
28
views
Size of circuit generating the solutions of a SAT problem
We have a satisfiable CNF formula $F$ which maps $\{0,1\}^n \to \{0,1\}$.
Let us call $S\in \{0,1\}^n$ the set of inputs that satisfy $F$, i.e. $F(s)=1 \, \forall s\in S$.
There is a circuit $C$ with $...
- 145
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 ...
- 17k
3
votes
1
answer
44
views
Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?
The problem:
Given two boolean formulas in 2-CNF, decide if they are equivalent.
I know that the problem is $\mathsf{coNP}$-hard when at least one formula is in 3-CNF. However, the same proof of $\...
D.W.♦
- 166k
1
vote
1
answer
56
views
Complexity of this variant of the Monotone(+,2−) -SAT problem?
In this post,Monotone$(+, 2^-)$-SAT problem is defined as follows:
Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $...
CommunityBot
- 1
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 \...
D.W.♦
- 166k
1
vote
1
answer
122
views
Reduce CNF-SAT to decision problem
Given CNF-SAT reduce it to the following decision problem:
Given n items, m groups (and for each group a set of items) and a ...
- 4,874
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
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
2
answers
61
views
Complexity of satisfiability for relational logic on the booleans
I know that propositional satisfiability is NP-complete and that if I add first-order quantifiers I get the complete problems for the polynomial hierarchy and PSPACE. What happens if my formulas are ...
- 2,204
0
votes
1
answer
25
views
How does the sumcheck protocol help solving the #SAT (circuit satisfiability) problem?
I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge"
He presents the Sumcheck protocol & then ...
D.W.♦
- 166k
4
votes
2
answers
3k
views
Unique SAT complexity clarification
Unique SAT is defined as:
Given any SAT problem, does the SAT problem have exactly 1 solution?
As I understand it is co-NPHard. I am unclear how it is in co-NP
Assuming the problem has more than 1 ...
- 2,041
1
vote
1
answer
109
views
Specialized SAT solver (?)
(Context)
Given two byte arrays of length 16, say $L$ and $H$, one can define a mapping $M$ from the set of all bytes to itself in the following way.
If $0 \le b \lt 256$ is a byte, let $\text{lo}(b)$ ...
D.W.♦
- 166k
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 ...
CommunityBot
- 1
-1
votes
1
answer
53
views
Schaefer's dichotomy theorem and limits on the formula length
Schaefer's dichotomy theorem ensures than when a constraint satisfiability problem satisfies certain conditions, the problem is either in $\mathsf P$ or is $\mathsf{NP}$-hard.
Suppose the following ...
D.W.♦
- 166k
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
11
votes
2
answers
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 ...
- 143
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
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 ...
2
votes
2
answers
384
views
Circuit satisfiability problem : SAT-C to SAT-2C
I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C.
Prove that ...
CommunityBot
- 1
1
vote
1
answer
111
views
Is Horn-SAT with XOR-relations NP-complete?
I was wondering if the combination of Horn-SAT and XOR-SAT is solvable in polynomial time or not.
It seems they can be solved in polynomial time as both are in class P and also that Horn-SAT is P-...
- 43
1
vote
1
answer
27
views
Are the indices of variables in the formula variable?
Let $L$ be an arbitrary language in $\Sigma_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\...
- 2,992
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
1
answer
125
views
Understanding the Strong Exponential Time Hypothesis
Let $n$ be the number of variables in the input formula and $m$ the number of clauses. Define $s_k = \inf\{\delta : k\text{-SAT can be solved in } 2^{\delta n} \text{ time}\}$. The strong exponential ...
D.W.♦
- 166k
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
0
votes
1
answer
219
views
Why solving #2SAT in polynomial time implies P = NP?
The wikipedia article for #P states that if we have a polynomial-time algorithm for a #P-complete problem, P = NP is true.
As #2SAT is #P-complete, this would mean that providing a polynomial-time ...
- 17k
3
votes
2
answers
3k
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 ...
CommunityBot
- 1
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 : ...
- 947
2
votes
4
answers
2k
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
1
answer
84
views
Is ANF-SAT P or NP?
Given a finite set of equations in ANF, for example:
$$
\begin{cases}
(x_1 \land x_2) \oplus (x_1 \land x_3 \land x_4) \oplus 1 = 0 \\
x_3 \oplus (x_2 \land x_3 \land x_4) = 0 \\
(x_1 \land x_4) \...
D.W.♦
- 166k
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)....
- 39.1k
1
vote
1
answer
138
views
MSAT and IMSAT problems (restricted versions of SAT)
I was reading about about NP-intermediate problems on Wikipedia and saw the IMSAT problem mentioned over there.
There is no Wikipedia page for that problem and they only cite this paper.
In the paper ...
CommunityBot
- 1
0
votes
2
answers
706
views
Reduce Subset-Sum to Sat
Is there a reduction from SUBSET-SUM to SAT?
Just general SAT, not 3-SAT.
Also the given multiset S only has positive integers.
SUBSET-SUM is defined as follows:
Input: a multiset S = { x1 , ... , xn }...
- 311
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
0
votes
1
answer
561
views
Time-complexity of evaluating a CNF formula
Given a Boolean formula over $n$ variables in CNF and a partial assignment to it, all the algorithms I can think of to evaluate the assignment run in time $\Theta(n^2)$. Is it possible to do it in $O(...
CommunityBot
- 1
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
2
votes
1
answer
348
views
Complexity of the (Complete/Assign) 3-SAT problem?
A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies.
Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a ...
- 279k
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$ ...
D.W.♦
- 166k
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