God's number is...

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:
This cannot possibly work...

I can't wait for one of our mathematicians to come in here and explain it.
 
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.
 
d4m4s74 said:
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...
Click to expand...

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:
aronpm said:
Why not?
Click to expand...

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.
 
Owen said:
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.
Click to expand...

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"
 
Stefan said:
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.
Click to expand...

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.
 
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.
 
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
 
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:
You must log in or register to reply here.

Similar threads

B
God's number for the FTO
Replies
10
Views
776
BadDisplayName
B
iguana
What is God's number for a 3-gen scramble?
Replies
8
Views
628
Bruce MacKenzie
Bruce MacKenzie
A
4x4x4 OBTM (WTM) upper bound improved from 55 to 54
Replies
1
Views
407
SpeedCubingLord
SpeedCubingLord
D
God's Number and Pieces Rubik's Cube
Replies
5
Views
628
Deleted member 27249
D
C
Man's number challenge
Replies
6
Views
1,026
CubingKid
C
Back
Top