Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/930787874462629888
added 1 character in body
Source Link
HardFork
HardFork
  • 534
  • 4
  • 11

The following theorem (from "The Design of approximation algorithm"algorithms" by Williamson & Shmoys, pg 43) states:

For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

The following theorem (from "The Design of approximation algorithm" by Williamson & Shmoys, pg 43) states:

For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states:

For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

Source Link
HardFork
HardFork
  • 534
  • 4
  • 11

How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?

The following theorem (from "The Design of approximation algorithm" by Williamson & Shmoys, pg 43) states:

For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?