# Return to Answer

 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 68, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}