2 edited body edited Oct 23 '13 at 19:59 Ron Teller 35822 silver badges88 bronze badges Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems. Here's a well-known example: Assume an algorithm $$A$$ yields an approximation $$\rho$$ to the TSP in polynomial time. Let $$G$$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem). Let $$G'$$ be a complete graph with the same vertices as in $$G$$ ($$V(G) = V(G')$$). Connect each two vertices in $$G'$$ with an edge $$e=(u,v)$$ with weight 10 if $$e$$ belong to $$E(G)$$, otherwise $$e$$ has a weight of $$\rho+1$$. Now find an approximation to the TSP on $$G'$$ by using $$A$$, if $$A$$ produced a solution that is $$< \rho+1$$, we can determine that there's an Hamiltonian Path in $$G$$, otherwise, there isn't. We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard. Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems. Here's a well-known example: Assume an algorithm $$A$$ yields an approximation $$\rho$$ to the TSP in polynomial time. Let $$G$$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem). Let $$G'$$ be a complete graph with the same vertices as in $$G$$ ($$V(G) = V(G')$$). Connect each two vertices in $$G'$$ with an edge $$e=(u,v)$$ with weight 1 if $$e$$ belong to $$E(G)$$, otherwise $$e$$ has a weight of $$\rho+1$$. Now find an approximation to the TSP on $$G'$$ by using $$A$$, if $$A$$ produced a solution that is $$< \rho+1$$, we can determine that there's an Hamiltonian Path in $$G$$, otherwise, there isn't. We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard. Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems. Here's a well-known example: Assume an algorithm $$A$$ yields an approximation $$\rho$$ to the TSP in polynomial time. Let $$G$$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem). Let $$G'$$ be a complete graph with the same vertices as in $$G$$ ($$V(G) = V(G')$$). Connect each two vertices in $$G'$$ with an edge $$e=(u,v)$$ with weight 0 if $$e$$ belong to $$E(G)$$, otherwise $$e$$ has a weight of $$\rho+1$$. Now find an approximation to the TSP on $$G'$$ by using $$A$$, if $$A$$ produced a solution that is $$< \rho+1$$, we can determine that there's an Hamiltonian Path in $$G$$, otherwise, there isn't. We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard. 1 answered Oct 23 '13 at 19:49 Ron Teller 35822 silver badges88 bronze badges Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems. Here's a well-known example: Assume an algorithm $$A$$ yields an approximation $$\rho$$ to the TSP in polynomial time. Let $$G$$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem). Let $$G'$$ be a complete graph with the same vertices as in $$G$$ ($$V(G) = V(G')$$). Connect each two vertices in $$G'$$ with an edge $$e=(u,v)$$ with weight 1 if $$e$$ belong to $$E(G)$$, otherwise $$e$$ has a weight of $$\rho+1$$. Now find an approximation to the TSP on $$G'$$ by using $$A$$, if $$A$$ produced a solution that is $$< \rho+1$$, we can determine that there's an Hamiltonian Path in $$G$$, otherwise, there isn't. We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard.