All Questions
12 questions
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
-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
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
1
vote
1
answer
37
views
Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters
I am looking for the computational complexity of the following problem.
Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same ...
- 21
0
votes
1
answer
100
views
What is the complexity of the following problem?
Input: $M$ is non deterministic Turing machine that always halts in $cn^k$ moves/steps, where $c$ and $k$ are constants and $n$ is the length of the input string of $M$, $w$ is any string in $\Sigma^*$...
user82913
2
votes
1
answer
408
views
Reduce the following decision problem to CNF-SAT
Input:
$X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$}
$Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$}
$k$, where, $k$ $\leq$ $m$
Output (Yes/No):
Satisfying the following condition, can all the elements in set $X$ be ...
- 87
3
votes
1
answer
1k
views
How exactly does a Max 2 Sat reduce to a 3 Sat?
I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
- 133
3
votes
3
answers
10k
views
Why is SAT in NP?
I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?
- 419
6
votes
2
answers
2k
views
Is the $k$P$k$N-3SAT problem NP-complete?
Consider the following 3-SAT variant defined over the variables $x_1,\ldots,x_n$. In the $k$P$k$N-3SAT problem each variable $x_j$, $j \in [n]$, occurs exactly $k$ times as a positive literal in $\phi$...
- 22.8k
9
votes
1
answer
1k
views
Complexity of (SAT to 3-SAT) Problem?
It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible (...
- 521
7
votes
2
answers
2k
views
3-SAT where variables occur equally many times as a positive literal and as a negative literal
Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$.
Is it NP-...
- 22.8k
6
votes
1
answer
394
views
Complexity of deciding the satisfiability of a quasi-monotone CNF formula
A quasi-monotone CNF formula is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal).
What is the complexity of deciding its ...
- 521