[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.