3 ms·
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 u
by bheadmaster 4y ago
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 4y agoI 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 4y agoDepends 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.