שנה שפה

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

היכנס אל מתיגון

אוֹ

חשבון חדש     אפס הסיסמה     

Graphs and NetworksAnts

The Travelling Salesman problem is NP-hard

Computational complexity theory is about determining how “difficult” problems are to be solved by a computer. NP hard (non-deterministic polynomial-time hard) is the class of the most difficult problems.

, which means that it is very difficult to be solved by computers (at least for large numbers of cities).

Finding a fast and exact algorithm would have serious implications in the field of computer science: it would mean that there are fast algorithms for all NP-hard problems. It would also render most of Internet security useless, which relies on the fact that certain problems are believed to be very difficult for computers.

Finding a fast algorithm to solve the Travelling Salesman problem would also solve one of the most famous open problems in mathematics and computer science, the P vs NP problem. It is one of the seven Millennium Prize Problems

The seven Millennium prize problems are some of the most difficult open problems in Mathematics. They were listed in 2000 by the Clay Mathematics Institute, and each hold a $1m reward:

  • P vs NP
  • The Hodge conjecture
  • The Poincaré conjecture
  • The Riemann hypothesis
  • Yang-Mills existence and mass gap
  • Navier-Stokes existence and smoothness
  • The Birch and Swinnerton-Dyer conjecture

So far, just one of the problems, the Poincaré conjecture, has been solved. However the mathematician who solved it, Grigori Perelman, declined the award.

, each carrying a $1m prize.

קורס מלא