• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

God's number is...

d4m4s74

Member
Joined
Nov 12, 2008
Messages
726
Location
Holland
WCA
2009ZALI01
YouTube
Visit Channel
my math is off, what's god's number on the 3x3x3 according to this?

I mean, if I take Θ(n^2/log n), change the n into 3 (I assume that's correct because they're talking about nxnxn puzzles) I get Θ(3^2/log 3) which according to wolphram alpha equals 1. that can't be it...
 
Last edited:
O

Owen

Guest
This cannot possibly work...

I can't wait for one of our mathematicians to come in here and explain it.
 

Goosly

Member
Joined
Feb 8, 2011
Messages
804
Location
Belgium
WCA
2010VERE01
I'm curious for a simplified summary of the paper :) I don't like reading theoretical things like this anymore, especially since my exams ended only 2 days ago.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
my math is off, what's god's number on the 3x3x3 according to this?

I mean, if I take Θ(n^2/log n), change the n into 3 (I assume that's correct because they're talking about nxnxn puzzles) I get Θ(3^2/log 3) which according to wolphram alpha equals 1. that can't be it...

You're ignoring the Θ and thus the constant factors. See here for a definition/explanation:

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

It's not a formula where you can just plug in a number and get an output number. That's not what this is about. No, it tells you that God's numbers have a lower bound of (n^2/log n)*k1 and an upper bound of (n^2/log n)*k2, for some positive constants k1 and k2. This isn't particularly useful to get God's number for a specific n, this is all about the *general* case of nxnxn.

It's similar to saying that "bacteria colonies grow exponentially" or "your hair grows linearly". You don't get exact numbers, but it does tell you the "kind" of growth speed.
 
Last edited:
O

Owen

Guest

Because the way the previous posters interpreted it, it made no sense that you could just plug a number into this simple formula, and get god's number.
This was later confirmed by Stefan Pochmann.
 

aronpm

Member
Joined
Sep 9, 2009
Messages
2,010
Because the way the previous posters interpreted it, it made no sense that you could just plug a number into this simple formula, and get god's number.
This was later confirmed by Stefan Pochmann.

Previous posters... a 12 year old and someone who copy+pasted it to W|A? Learn what the big theta notation means before you say "it's not possible"
 

d4m4s74

Member
Joined
Nov 12, 2008
Messages
726
Location
Holland
WCA
2009ZALI01
YouTube
Visit Channel
You're ignoring the Θ and thus the constant factors. See here for a definition/explanation:

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

It's not a formula where you can just plug in a number and get an output number. That's not what this is about. No, it tells you that God's numbers have a lower bound of (n^2/log n)*k1 and an upper bound of (n^2/log n)*k2, for some positive constants k1 and k2. This isn't particularly useful to get God's number for a specific n, this is all about the *general* case of nxnxn.

It's similar to saying that "bacteria colonies grow exponentially" or "your hair grows linearly". You don't get exact numbers, but it does tell you the "kind" of growth speed.

Thanks for the clarification, I should have read more then just the abstract.

Damn, ever since I dropped out I started forgetting a lot, I learned about and used the big O less then a year ago.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I looked at the paper, and it was impressive, but not as amazing as it sounded. I have a mixed reaction to the God's Number result; on one hand, it's cool that they established a better upper bound (i.e. a better general solution), but on the other hand establishing something is Θ(n^2/log n) is only useful for computability theorists. It's an interesting-sounding result, but doesn't really have much practical use IMO, because saying that some sequence follows a particular pattern of growth as it goes to infinity doesn't tell us anything about individual values, and we only have two values of the series calculated anyway (11, 20, ...) with a third being very far off.

The "optimal solution of a*b*n can be found in polynomial time on n" result is similar; it sounds interesting, but it's only useful in a mathematical sense to establish a bound for the infinite series, and doesn't really make it easier to actually do the solving. The technique used in the proof relies on brute force, and while it is polynomial in n (it looks to be O(n) but I'm not sure) it involves extremely large constants and thus has no real practical use.
 

Jorghi

Member
Joined
Jun 9, 2011
Messages
448
Well the programs that say "20 moves or less" simply just use bruteforcing methods to solve the cube. Though we don't really know how optimal the moves are and because it could take a long time to find a better solution.

Unless there is pure mathematical proof :p xD ;P
 

kprox1994

Member
Joined
Nov 27, 2009
Messages
592
Location
Saint Louis, Missouri, United States
WCA
2017PAAR01
YouTube
Visit Channel
Scientists Develop an Algorithim to Solve Cubes of any Size.

Found this browsing engadget, pretty interesting. http://www.engadget.com/2011/07/01/scientists-develop-algorithm-to-solve-rubiks-cubes-of-any-size/&category=classic&altPost=alt&icid=eng_latest_art Can someone link this? It's too hard to do on my phone.
 
Last edited:
Top