Consider this problem: given positive integers a,b,c, are there positive integers x,y such that axx+b*y=c? Amazingly, it is NP-complete. Can anyone explain to me how it manages to be complete?

No, I (probably, given a reasonable time limit) can't. But wow. I didn't expect to see something that apparently simple NP-complete.