Did you actually read the paper? There's a mathematical definition of complexity that is used, and on that metric it is shown to be far harder than any other previously analyzed game.
Of course by now the title and even the submission link has completely changed (it was linked to an article before).