New answers tagged

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