The Naked Scientists
Toggle navigation
Login
Register
Podcasts
The Naked Scientists
eLife
Naked Genetics
Naked Astronomy
In short
Naked Neuroscience
Ask! The Naked Scientists
Question of the Week
Archive
Video
SUBSCRIBE to our Podcasts
Articles
Science News
Features
Interviews
Answers to Science Questions
Get Naked
Do an Experiment
Science Forum
Ask a Question
About
Meet the team
Our Sponsors
Contact us
User menu
Login
Register
Search
Home
Help
Search
Tags
Recent Topics
Lonely Topics
Login
Register
Naked Science Forum
Non Life Sciences
Physics, Astronomy & Cosmology
Travelling Salesman problem
« previous
next »
Print
Pages: [
1
]
Go Down
Travelling Salesman problem
10 Replies
5616 Views
0 Members and 1 Guest are viewing this topic.
showmen
Jr. Member
21
Activity:
0%
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.
Logged
Relph
First timers
8
Activity:
0%
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.
Logged
showmen
Jr. Member
21
Activity:
0%
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?
Logged
Relph
First timers
8
Activity:
0%
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 [
]
Logged
Relph
First timers
8
Activity:
0%
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
Logged
showmen
Jr. Member
21
Activity:
0%
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)?
Logged
Relph
First timers
8
Activity:
0%
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.
Logged
showmen
Jr. Member
21
Activity:
0%
Travelling Salesman problem
«
Reply #7 on:
02/03/2008 11:12:59 »
very good very good. good luck with your degree.
Logged
showmen
Jr. Member
21
Activity:
0%
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".
Logged
Soul Surfer
Naked Science Forum King!
3345
Activity:
0%
keep banging the rocks together
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.
Logged
Learn, create, test and tell
evolution rules in all things
God says so!
showmen
Jr. Member
21
Activity:
0%
Travelling Salesman problem
«
Reply #10 on:
04/03/2008 13:36:57 »
cheers soul surfer
Logged
Naked Science Forum
Travelling Salesman problem
«
Reply #10 on:
04/03/2008 13:36:57 »
Print
Pages: [
1
]
Go Up
« previous
next »
Tags:
There was an error while thanking
Thanking...