Depends on the problem, really. I've been out of school for half a decade now so I'm a little rusty too.

I remember that the Traveling Salesman can be constructed as "is the minimum path less than N" in which N represents the solution, not the size.