[suppressingfire]

But the getacoder poster only specified that it had to be done in polynomial time, and didn't clarify whether that had to be total CPU time (i.e., "work") or wall clock time.

Given that underspecification, it's perfectly justifiable to use an exponential amount of resources to achieve the goal.