Nitpick: Decision problems only have yes/no answers ("is there a solution that satisfies P, with score >= X"); problems that ask for actual solutions with a mor

Nitpick: Decision problems only have yes/no answers ("is there a solution that satisfies P, with score >= X"); problems that ask for actual solutions with a more complicated structure ("find a solution that satisfies P, with score >= X") are function problems, not decision problems. Interestingly, even though the solution to a decision problem only gives you 1 bit of information, for all NP problems I'm aware of, solving a polynomial number of problem instances is still enough to recover a full solution. For example, suppose we're looking for a maximum clique in a graph. First, binary search as you describe to find the size of the maximum clique. Call that size X. Then to find an actual clique of size X, repeat the following for each vertex v in the graph, in any order: 1. Tentatively delete v and solve the problem "Is there now a clique of size >= X?". 2. If the answer is yes, delete v permanently: we can ignore it from this point on since there is some X-clique that avoids it, and we already know from our initial binary search that that clique is best-possible. 3. If the answer is no, v must belong to every X-clique in the graph. We can't do without it, so reinstate it in the graph. Afterwards, exactly X vertices will remain -- the vertices of some maximum clique in the original graph.