All Questions
Tagged with complexity-theory satisfiability
267 questions
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 ...
- 3
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 ...
- 15
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
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 ...
- 23
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^{\...
- 141
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
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
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 $\...
- 2,041
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
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 ...
- 183
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 ...
- 125
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)$ ...
- 145
-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 ...
- 2,041
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 ...
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 ...
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
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 $...
- 43
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 ...
- 25
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
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
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 ...
- 195
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) \...
- 13
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
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
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
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
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
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 ...
- 148
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 ...
- 521
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
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(...
- 239
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
2
votes
2
answers
185
views
Exponential Time Hypothesis and the input size vs number of variables
According to Exponential Time Hypothesis there does not exist a deterministic algorithm to solve SAT over $V$ variables in time $o(2^V)$. However, let's say the number of literals $n = \omega(poly(V))$...
- 2,041
1
vote
1
answer
96
views
Proving the NP hardness of two variants of SAT
$k$-$\text{RSAT}$ is a variant of $k$-$\text{SAT}$ where we restrict our attention to formulae in
which each variable occurs at most $3$ times, and each literal occurs at most twice. The language
$k$-$...
- 443
1
vote
1
answer
70
views
Proving 2SAT is in P vs algorithm for finding a satisfying assignment
I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path ...
- 113
2
votes
1
answer
62
views
expected running time of Randomwalk for k-SAT
model: gambler ruin theorem.
A gambler has $i$ coins initially, in every step, he wins a coin with probability $p$, and loses a coin with probability $1-p$. The expected time that he loses all his ...
- 399
0
votes
1
answer
100
views
Is there a version of the boolean satisfiability problem that has NC complexity?
Boolean satisfiability problem (SAT) is NP-complete by Cook–Levin theorem. (wiki)
Horn-satisfiability – given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's ...
- 309
2
votes
1
answer
58
views
Satisfiability of bounded assignment of input variables to CNF formula
Consider a CNF formula $F$ such that all the literals in every clause must be negative ( here is an example : $F$ = ($\bar{x_{1}}$ $\wedge$ $\bar{x_{2}}$) $\vee$ ($\bar{x_{3}}$ $\wedge$ $\bar{x_{4}}$ $...
- 49
1
vote
0
answers
49
views
Conflict Clusters – Another P=NP Proof [closed]
Conflict Clusters – Another P=NP Proof
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a ...
- 371
2
votes
1
answer
353
views
Reducing a CNF formula to a DNF formula in less than exponential time
The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently.
My idea is based upon the ...
- 364