• 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 30,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...

Joined
Nov 12, 2008
Messages
722
Likes
2
Location
Holland
WCA
2009ZALI01
YouTube
d4m4s74
#2
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:
Joined
Nov 2, 2009
Messages
1,141
Likes
4
#3
This cannot possibly work...

I can't wait for one of our mathematicians to come in here and explain it.
 
Joined
Feb 8, 2011
Messages
804
Likes
45
Location
Belgium
WCA
2010VERE01
#5
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.
 
Joined
May 7, 2006
Messages
7,287
Likes
38
WCA
2003POCH01
YouTube
StefanPochmann
#6
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:
Joined
Nov 2, 2009
Messages
1,141
Likes
4
#7
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.
 
Joined
Sep 9, 2009
Messages
2,010
Likes
4
#8
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"
 
Joined
Nov 12, 2008
Messages
722
Likes
2
Location
Holland
WCA
2009ZALI01
YouTube
d4m4s74
#10
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.
 
Joined
Dec 18, 2007
Messages
7,830
Likes
31
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
#14
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.
 
Joined
Jun 9, 2011
Messages
448
Likes
0
#15
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
 
Joined
Nov 27, 2009
Messages
592
Likes
23
Location
Saint Louis, Missouri, United States
WCA
2017PAAR01
YouTube
kprox1994
#19
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