Re: As for that time...
"Since the robot in the video would be totally unable to solve a 4x4x4 cube, I'd say that the complexity in this case is "worse than exponential"."
Now I see what the previous commentator might have meant: the nxnxn cube, whether finding the optimal solution is in P. I very much doubt if it's in NP, and since the symmetric group on n points has order n!, I would hazard a guess it's not soluble in O(a^n) time for any a>0.