[bheadmaster]

All I've seen pretty much can.

Each solution can be encoded as an integer, and as long as you can construct your query as "is solution less than N?", you can use binary search to solve the problem in log(n) repetitions of the query, which does not affect the complexity class.

[Scea91]

I am a bit rusty on this theory but isn't the N in your case related to the output size while you would need it to be related to input size instead?

[bheadmaster]

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.