SAT and the travelling salesman have not been proven to be in P. They're both NP-Complete, which means that if they/are/ in P, then P = NP. While it's very likely that neither are in P, it's still far from being fact.
You can trisect an angle.
You need a/ruler/, not just a straightedge, however.
http://www.cs.unb.ca/~alopez-o/math-faq/mathtext/n ode28.html
Get your List-O-Impossible-Things right!;)
Dave
Computability stuff I'd term more as "math", like the Halting Problem, etc. There/is/ a difference between programming and computer science, but I think more about computer science as having a combinatorial bent. Knuth's "Art of Computer Programming" books are a little closer to "computer science" than just the high-up language things.
Computer Science is just math with a more applied tilt.
"There ought to be limits to freedom," - GW Bush
That Bushism wasn't taken from a normal speech about criminals. It's in reference to him filing a lawsuit against a parody website (www.gwbush.com). You can get the mp3 of his speech from there, I believe.
Dave
Re:I'm a Maths Graduate but ...
on
Does P = NP?
·
· Score: 1
You're thinking of something more along the lines of the Travelling Salesman problem. Given an undirected, weighted graph, the problem is to find the lowest-cost Hamiltonian cycle (a path that visits all the nodes on the graph without taking the same edge twice, ultimately returning to its beginning).
Finding a Hamiltonian cycle alone is NP-Complete. Adding the weighted edges in there doesn't help.;)
Dave
Re:I'm a Maths Graduate but ...
on
Does P = NP?
·
· Score: 1
> there are some problems (such as the Halting
> Problem) that are formally undecidable - not
> solvable in polynomial time even on a
> non-deterministic computer
The Halting Problem is unsolvable on any computer, by any computation model, exponential time or not, to my knowledge (I haven't taken the class my school offers in automata, but I've done a bit or reading).
I've been following these contests since they came out, and they're genuinely interesting. However, one of the major problems with them is that so many are "joke" games, so you really can't get to the meat of the best games out there. Usually there are two or three very high-quality games released with each contest (in my view).
Check out ftp.gmd.de/if-archive for a whole bunch. The best are by Graham Nelson and Andrew Plotkin - "Spider and Web" is a personal favorite.
But then again, I'm one of those freaks that thinks Zork Zero was the epitome of computer gaming.;)
Slashdot Mirror
The halting problem isn't in NP (this was proved by Turing). Since P subset NP, the halting problem can't in P either.
SAT and the travelling salesman have not been proven to be in P. They're both NP-Complete, which means that if they /are/ in P, then P = NP. While it's very likely that neither are in P, it's still far from being fact.
You can trisect an angle. You need a /ruler/, not just a straightedge, however.
http://www.cs.unb.ca/~alopez-o/math-faq/mathtext/n ode28.html
Get your List-O-Impossible-Things right! ;)
Dave
Computability stuff I'd term more as "math", like the Halting Problem, etc. There /is/ a difference between programming and computer science, but I think more about computer science as having a combinatorial bent. Knuth's "Art of Computer Programming" books are a little closer to "computer science" than just the high-up language things.
Computer Science is just math with a more applied tilt.
"There ought to be limits to freedom," - GW Bush That Bushism wasn't taken from a normal speech about criminals. It's in reference to him filing a lawsuit against a parody website (www.gwbush.com). You can get the mp3 of his speech from there, I believe. Dave
You're thinking of something more along the lines of the Travelling Salesman problem. Given an undirected, weighted graph, the problem is to find the lowest-cost Hamiltonian cycle (a path that visits all the nodes on the graph without taking the same edge twice, ultimately returning to its beginning).
;)
Finding a Hamiltonian cycle alone is NP-Complete. Adding the weighted edges in there doesn't help.
Dave
> there are some problems (such as the Halting
> Problem) that are formally undecidable - not
> solvable in polynomial time even on a
> non-deterministic computer
The Halting Problem is unsolvable on any computer, by any computation model, exponential time or not, to my knowledge (I haven't taken the class my school offers in automata, but I've done a bit or reading).
Dave
I've been following these contests since they came out, and they're genuinely interesting. However, one of the major problems with them is that so many are "joke" games, so you really can't get to the meat of the best games out there. Usually there are two or three very high-quality games released with each contest (in my view).
;)
Check out ftp.gmd.de/if-archive for a whole bunch. The best are by Graham Nelson and Andrew Plotkin - "Spider and Web" is a personal favorite.
But then again, I'm one of those freaks that thinks Zork Zero was the epitome of computer gaming.
Dave