MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
December 28th, 2010 at 1:23:58 PM permalink
Quote: odiousgambit

Regarding the solution, why is it that modern computers don't help? If it is a problem of tediousness of examining all possibilities, could a program written for a computer [a super computer?] get that job done for this problem or other such problems?



There is actually a large class of problems for which brute-force computational analysis is simply insufficient. Some of them, like this one, grow exponentially in complexity as the number of examinations increases. For example, if you were playing Klondike with 8 cards (just the kings and queens), you might have a reasonably easy go of it. Add in the jacks and it gets harder. Add in the tens and it gets much, much harder than going from queens to jacks. Add in the nines and it gets even harder still. Before long, you reach a problem the complexity of which is beyond the capability of modern computer analysis, even if you ran it as fast as possible. To put things in perspective, work has been done to demonstrate that there are somewhere around
45193640626062205213735739171550309047984050718
different positions in the game of chess. In comparison, the age of the universe is around
432329886000000000000000000
nanoseconds. So even if you had a computer that could perform one evaluation per nanosecond, and that computer magically sprang into being at the beginning of time, it would take over 100000000000000000000 times the age of the universe to "solve" chess.

Klondike isn't as difficult, but it's still harder than can be dealt with directly.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
odiousgambit
odiousgambit
Joined: Nov 9, 2009
  • Threads: 270
  • Posts: 7037
December 28th, 2010 at 1:48:19 PM permalink
wow

fascinating, thanks
Baccarat is a game whereby the croupier gathers in money with a flexible sculling oar, then rakes it home. If I could have borrowed his oar I would have stayed. ~Mark Twain
FleaStiff
FleaStiff
Joined: Oct 19, 2009
  • Threads: 204
  • Posts: 10468
December 28th, 2010 at 1:59:13 PM permalink
Quote: MathExtremist

There is actually a large class of problems for which brute-force computational analysis is simply insufficient. Some of them, like this one, grow exponentially in complexity as the number of examinations increases.

Surely all this N, P, NP, NPhard, Polynomial time, Traveling Salesman Problem stuff has been getting less daunting as chip speeds and capacities increase. What about all these clusters and memristor stuff?

I've never felt good about calling a problem impossible to solve merely because so far its not been solved.
avargov
avargov
Joined: Aug 5, 2010
  • Threads: 16
  • Posts: 615
December 28th, 2010 at 4:08:39 PM permalink
Where is Paul Erdos when you really need him....
Before you diagnose yourself with depression or low self-esteem, first make sure that you are not, in fact, just surrounded by assholes." ~ William Gibson
rxwine
rxwine
Joined: Feb 28, 2010
  • Threads: 146
  • Posts: 6041
December 28th, 2010 at 4:17:39 PM permalink
Quote: MathExtremist

To put things in perspective, work has been done to demonstrate that there are somewhere around
45193640626062205213735739171550309047984050718
different positions in the game of chess.



That number is probably being used as a password for encrypted documents somewhere. If you misplace it, you could probably look it up on the Internet.
It's so overt, it's covert.
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
December 28th, 2010 at 5:50:20 PM permalink
Quote: FleaStiff

Surely all this N, P, NP, NPhard, Polynomial time, Traveling Salesman Problem stuff has been getting less daunting as chip speeds and capacities increase. What about all these clusters and memristor stuff?

I've never felt good about calling a problem impossible to solve merely because so far its not been solved.



Not impossible, intractable. An exponential-time algorithm for solving a problem makes it "possible" to solve, but not tractable for all N. Regardless of how fast chips get, you're still talking about an insignificant improvement relative to the number of computations in an exponential-time problem. So for the TSP, for example, whether a fast computer can solve for N=1000 or 10000 is irrelevant to the question of whether TSP is computationally complex given the current model of computation.

If someone develops a computer that is not computationally-reducible to a Turing machine, that may change the underlying theory. But until then, the whole premise of complexity theory is still sound and that means "hard" problems are "hard" regardless of whether small examples of them have practical solutions.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
Mosca
Mosca
Joined: Dec 14, 2009
  • Threads: 169
  • Posts: 3351
December 29th, 2010 at 6:53:16 AM permalink
Quote: MathExtremist

I'm pretty sure this is how they offered it in casinos, back in the day. Klondike is one of the statutorially-defined gambling games in Nevada. See NRS 463.0152.



Back in the '60s, my grandfather taught me how to play Klondike, and he kept score with matchsticks that way; he called it "the Vegas way". He was a long time gambler, his cousin (my mother's Uncle Joe) supplied cigarette-, candy-, and slot machines to bars in Pittsburgh's East End. I actually had a working old time slot machine for years, I sold it in the early '90s. (It was a Jennings fruit machine, "Big Chief", took quarters, all mechanical. I wish I had it now, or at least a picture of it. Oh, well.)
NO KILL I
odiousgambit
odiousgambit
Joined: Nov 9, 2009
  • Threads: 270
  • Posts: 7037
March 13th, 2017 at 3:20:33 AM permalink
Quote: rxwine

That number is probably being used as a password for encrypted documents somewhere. If you misplace it, you could probably look it up on the Internet.



https://www.google.com/#q=45193640626062205213735739171550309047984050718&*

not sure why that doesn't turn into a hyperlink
Baccarat is a game whereby the croupier gathers in money with a flexible sculling oar, then rakes it home. If I could have borrowed his oar I would have stayed. ~Mark Twain

  • Jump to: