New answers tagged np-hard
2
Look at the statement of Cook's theorem: it states that for any problem in NP, there exists a reduction from that problem to 3SAT. The key part is the "there exists". The proof only needs to show that there exists such a reduction. For these purposes, it suffices to note that there exists a $k$ such that $M$ runs in time $O(n^k)$. There is no ...
0
The definition of NP-Hard states: "A problem $L$ is NP-Hard, if for every problem $L'\in NP$, there exists a polynomial reduction from $L'$ to $L$, namely - $L'\le_p L$".
Now, since $A$ is NP-Hard, that would mean that for any $L'\in NP$, we have $L'\le_p A$. Since the relation $\le_p$ is transitive (prove it!), we also have $L'\le_p B$. Hence, by ...
1
For vertex cover: start with an empty vertex cover $S$. Iteratively consider the edges of the graph. For each edge $e=(u,v)$, check if $\{u,v\} \cap S = \emptyset$. If that's the case we say that $e$ is special and we add both $u$ and $v$ to $S$.
At the end of the algorithm $S$ is a vertex cover containing at most twice as many vertices as a minimum vertex ...
2
Considering it as the entire set of NP as you said according to this statement:
A problem X is NP-hard if every problem Y ∈NP reduces to X.
Since P1, P2,...Pn can all be reduced to PP1, PP1 is a NP Hard Problem.
Now we have a)PP1 reducible to PP2 and b)PP2 reducible to some NP problem.
According to this:
A reduction from problem A to problem B is a ...
Top 50 recent answers are included