The Naked Scientists

The Naked Scientists Forum

Author Topic: Travelling Salesman problem  (Read 5387 times)

Offline showmen

  • Jr. Member
  • **
  • Posts: 21
    • View Profile
Travelling Salesman problem
« on: 28/02/2008 21:25:30 »
I know this is really a mathematical issue but there's nowhere else that I know where to post this!

http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2007/03/11/TRG5FOH4LP1.DTL [nofollow]

Do people know of any other interesting examples. I know of something similar that applies to phylogenetics and tree searching and that it's a big problem.


 

Offline Relph

  • First timers
  • *
  • Posts: 8
    • View Profile
Travelling Salesman problem
« Reply #1 on: 29/02/2008 08:24:07 »
You actually hit the jackpot! The Traveling Salesman Problem is part of a list of special problems known as NP-Complete problems. So, what's so big about them? They are central to one of the most important unsolved problems in both mathematics and computer science, known as P=NP?
P=NP? is a problem that basically asks: are difficult or consuming problems really that hard? When we found something that takes to much time to found out, is it that we looked the wrong way?
Let's give an example. Sudoku: to solve sudoku, you can go ahead and try all possible number combinations, but that will take a lot of time. You can usually solve a 9x9 sudoku easily in other ways. But if you make a bigger sudoku, the usual methods won't do, and the problem will take a lot of time to solve.
So we have 3 different concepts here:

-P: those are a list of all problems that can be solved in a reasonable amount of time by a computer. This is define precisely in a mathematics, but we really don't need to go there.

-NP: These, on the other hand, are problems where you can check if an answer is a correct one in a reasonable amount of time. For example, if they ask you if a sudoku is correct, you can easily scan the boxes to see that everything is correct.

-NP-Complete: This are the hardest problems of NP. Basically, if you were to prove that one of this problems can be solve easily, you'll be able to prove that all NP problems are easy, so NP=P.

What's so big about NP=P? A lot of things. But probably the most important one for everyone has to do with security. Nowadays, all transactions over the net rely on the difficulty of difficult problems. If you were to prove that difficult problems can be solved easily (that is, NP=P), the world won't be able to rely on any reasonable security protocol, so I guess civilization as we know it will collapse.
You can find more of these problems all over the internet, as I told you, these are the big thing. As a matter of fact, if you were able to prove either that NP=P or NP≠P, then you might be able to get $1 million dollars from the Clay Mathematics institute.
 

Offline showmen

  • Jr. Member
  • **
  • Posts: 21
    • View Profile
Travelling Salesman problem
« Reply #2 on: 29/02/2008 17:16:15 »
that's really cool actually, thanks. In your opinion, is it possible that P=NP for difficult problems? Also, is it certain that if this is proved for ONE NP-complete problem, then it's true for all?
 

Offline Relph

  • First timers
  • *
  • Posts: 8
    • View Profile
Travelling Salesman problem
« Reply #3 on: 01/03/2008 08:34:59 »
Mathematically, there are three possible answers to the P=NP? problem. It can either be true, false or undecidable. As a mathematical statement, the problem is completely abstract and doesn't need to apply completely on real life.
As such, I personally believe that either P≠NP, or that it is undecidable.
P≠NP is probably the most accept position mainly because we haven't been able to improve algorithms to make this hard problems easy. Now, that really doesn't mean anything, as fairly simple theorems on mathematics might take a long time to solve, for example Fermat's Last Theorem (which took over 3 centuries).
On the other hand, by undecidable we mean that with the current axiomatic, we cannot prove that it either is true or false. Some deep results in mathematics have been proved to be undecidable, such as the axiom of choice or the continuum hypothesis. The reason I believe this to be a strong possibility is because P vs NP also tells us something about proofs of mathematical theorems.
That's actually what made me interested in these fields the first time. Theoretical computer science is deeply related to the concept of what can or can't be done in mathematics. We have come to realized in the last 100 years that math is very similar to a computer. The biggest result in this sense is probably the halting problem, which basically says that we cannot know if any given program will eventually halt.
That's actually the mathematical reason why P=NP? is important. I gave you before one of the practical reasons, other being that there a a lot of problems in logistics (such as the TSP), biology (refer to the Protein Structure Prediction problem), and many other science areas that are part of NP.
So personally, I'm not sure; but then again, I'm no expert on the subject, at least not yet :)
 

Offline Relph

  • First timers
  • *
  • Posts: 8
    • View Profile
Travelling Salesman problem
« Reply #4 on: 01/03/2008 08:36:55 »
Oh, and also, That's what it actually means to be on NP-Complete: a problem on NP that if proved to be on P will mean that P=NP. So yeah, proving that only one NP-complete problem is on P means that every other is
 

Offline showmen

  • Jr. Member
  • **
  • Posts: 21
    • View Profile
Travelling Salesman problem
« Reply #5 on: 01/03/2008 12:27:46 »
 Very interesting. I was pondering this stuff again this morning when I was doing a sudoku- but then I realised that the "medium" sudoku in a free London paper probably doesn't count as an NP-complete problem.  ;)

Just out of interest, are you formally involved in mathematics or is it a "hobby" (for want of a better word)?
 

Offline Relph

  • First timers
  • *
  • Posts: 8
    • View Profile
Travelling Salesman problem
« Reply #6 on: 02/03/2008 06:13:13 »
Actually, when you talk about a problem being on P, NP, NP-complete or any other "Complexity Class" (as they are call, there's a bunch of them); you are talking of all the different instances of that problem, and you are usually looking at the worst case scenario. So basically, when you say Sudoku is NP-Complete, you are referring to all Sudokus as a single entity. That doesn't mean all Sudokus are hard to solve, but that there are sudokus that are incresingly hard to solve.
And yes, I'm finishing my Bachelor's degree on math. I'm actually hoping to get involved later on research regarding Complexity Theory and Logic.
 

Offline showmen

  • Jr. Member
  • **
  • Posts: 21
    • View Profile
Travelling Salesman problem
« Reply #7 on: 02/03/2008 11:12:59 »
very good  very good. good luck with your degree.
 

Offline showmen

  • Jr. Member
  • **
  • Posts: 21
    • View Profile
Travelling Salesman problem
« Reply #8 on: 03/03/2008 17:47:15 »
Hey, would you be able to explain to me what a "stochastic point process" is? I'm reading a paper about the probability of re-sigthing a supposedly extinct species is and I can't quite work out what is meant by a "stochastic point process".
 

Offline Soul Surfer

  • Neilep Level Member
  • ******
  • Posts: 3345
  • keep banging the rocks together
    • View Profile
    • ian kimber's web workspace
Travelling Salesman problem
« Reply #9 on: 03/03/2008 18:03:53 »
A stochastic process is essentially a process containing a random variable  (a bit like the uncertainty principle)  a point process is one that refers to a single point ie not a line or a plane or othe multidimensional structure.

I have a great interest in  "stochastic resonance" both in its association with signal processing for the analysis of data and the potential "evolution" of the laws of physics during the big bang.

 

Offline showmen

  • Jr. Member
  • **
  • Posts: 21
    • View Profile
Travelling Salesman problem
« Reply #10 on: 04/03/2008 13:36:57 »
cheers soul surfer
 

The Naked Scientists Forum

Travelling Salesman problem
« Reply #10 on: 04/03/2008 13:36:57 »

 

SMF 2.0.10 | SMF © 2015, Simple Machines
SMFAds for Free Forums