2 edited body
source | link

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
source | link

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.