My memory is failing me, but I think I heard a talk once where a (specific?) robot motion-planning problem is PSPACE-hard, aka in a class that contains the problems in NP. Maybe that's another way to articulate Moravec's paradox.