New answers tagged np-hard
5
Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ with $|V|=n$ and of an integer $k$.
Construct the graph $H = (V', E')$ where $V' = V \cup \{ x_{u,v} \, : \, (u,v) \in E \}$ and $E' = V' \times V'$.
For each $...
5
Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$.
For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is ...
2
For the first question: This is an open problem. If $\mathsf{P} \neq \mathsf{NP}$ then the answer is no: the decision version of 3-SAT is $\mathsf{NP}$-Complete, while Primality is in $\mathsf{P}$, the means that a Karp reduction from 3-SAT to Primality would imply $\mathsf{P}=\mathsf{NP}$.
For the second question:
Primality is in $\mathsf{P} \subseteq \...
2
Let $\langle G=(V, E), k \rangle$ be an instance of Independent Set, and call $n=|V|$.
Let $N$ be a set of $n+1$ new vertices (not in $V$), and construct a new graph $G' = (V', E')$ where $V' = V \cup N$ and $E' = E \cup (N \times V)$.
If $G$ has an Independent Set $S$ of size at least at least $k$ then $G'$ has a Triangle-Free set $S'$ of size at least $n+...
0
-In bin packing u have fixed size/weight trucks say K & want to find the min no. of them n to hold all the given goods.
-I take it u think of solving ur problem as it is bin packing to get n, then make all the rectangles scaled down to 1/n.
-Since rectangles can't be reshaped or even rotated, u see it as 2D bin packing.
-As start, u may solve 2 bin ...
1
You can reduce from 3SAT.
The graph has two parts. One part is the "variable" part. For each of the variables $v_1,\ldots,v_n$ there are two three vertices $v_i^+,v_i^-,v_i$, and this part consists of the following edges, for $i \in [n]$:
$$(v_{i-1},v_i^+),(v_{i-1},v_i^-),(v_i^+,v_i),(v_i^-,v_i)$$
Here $v_0$ is a new vertex, identified with $s_1$, and $...
2
Let $L$ be any language in NP. Since $A$ is NP-hard, there is a polytime reduction $f$ such that $x \in L$ iff $f(x) \in A$. We want to convert $f$ to a polytime reduction $g$ such that $x \in L$ iff $g(x) \in A \cup B$.
What prevents $f$ from working? Let's consider three cases:
$f(x) \in A$. In this case, $f(x) \in A \cup B$ as well.
$f(x) \notin A$, and ...
2
Given an instance $x$ of $A$, reduce it to an instance $y$ of $A \cup B$ as follows:
Check (in polynomial time) if $x \in B$, if the answer is yes, then $x \not\in A$ since $A \cap B = \emptyset$. Pick any $y \in \Sigma^* \setminus (A \cup B)$ (which is non-empty by hypothesis).
If $x \not\in B$, then $x \in A \cup B \iff x \in A$. Pick $y=x$.
2
(other than bounding the complexity of verification to polynomial time).
This is exactly the reason the problems can be solved in exponential time. An algorithm can simply run the verification algorithm for all possible certificates to see if any one of them is a valid "solution". There are only exponentially many certificates since the definition of $NP$ ...
3
Intuitively, the difficulty of all $\mathsf{NP}$-Complete problems is related: solving any single $\mathsf{NP}$-Complete problem in time $O(t(n))$ immediately yields an algorithm for any other $\mathsf{NP}$-Complete problem with a running time of $O(t(\mbox{poly}(n)))$. This shows, for example, that either all $\mathsf{NP}$-Complete problems admit polynomial-...
Top 50 recent answers are included
