All Questions
21 questions
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
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
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 ...
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
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
8
votes
2
answers
3k
views
Is "Reachable Object" really an NP-complete problem?
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. ...
- 183
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
3
votes
1
answer
353
views
Having trouble understanding a proof of Mahaney’s theorem
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.
I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $...
- 57
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
1
vote
2
answers
5k
views
How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?
I am studying for NP problems.
To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
- 29
7
votes
2
answers
4k
views
3-SAT problem with number of clauses equal to number of variables
Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is ...
- 502
15
votes
2
answers
2k
views
MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?
What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard?
To formalize this more precisely, let
$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{...
D.W.♦
- 166k
1
vote
1
answer
224
views
Why Cook-Levin thorem's proof can mean SAT's NP-Hardness
I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ ...
- 13
21
votes
1
answer
4k
views
Proving that the conversion from CNF to DNF is NP-Hard
How can I prove that the conversion from CNF to DNF is NP-Hard?
I'm not asking for an answer, just some suggestions about how to go about proving it.
- 311
6
votes
1
answer
4k
views
Simple proof that circuit satisfiability problem is NP-Hard
$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.
$\cc = \{\langle C \rangle : C \text{ is a ...
- 1,037
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
1
vote
3
answers
162
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 ...
- 135
2
votes
0
answers
408
views
Is Max-2SAT with exactly 3 occurrences per variable APX-hard?
The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied.
The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in
at most 3 clauses (counting ...
- 530
2
votes
1
answer
3k
views
3-SAT to Max-2-SAT Reduction
I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck.
Let me first describe it.
3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in it, one ...
- 1,219
6
votes
1
answer
531
views
Is MIN or MAX-True-2-XOR-SAT NP-hard?
Is there a proof or reference that $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$?
Let:
$$\Phi\left(\mathbf x\right)={\huge\...
- 6,221
3
votes
1
answer
226
views
How can I identify that a restricted variant of Boolean SAT remains hard or not?
While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this variant (not mentioned there, but I ...
- 371