do we ever only care about the decision problem? I know of only one case of that

(I had been thinking of this for a post then Lance's post on search versus decision inspired me to write up these thoughts.)

When teaching NP-completeness we often say

The problem we really care about is, for example, given a weighted graph and two vertices s and t, find the optimal way to go from s to t while hitting every node. But its cleaner mathematically to look at the decision problem:

{ (G,s,t,C) : there is a Ham Path from s to t that costs \le C }

The search and decision are poly time equivalent, so its fine to just look at the decision. Indeed- if our interest in in lower bounds then clearly if Decision is hard then Find is Hard.

But here are some questions about search vs decision in general, not just with regard to P vs NP.

1) Is there ever a case where the real world actually cares about the decision version? I can think of just one- given a number is it PRIME is used in Crypto. The real world does not need the witness that its prime (or similar).  They  just want a prime.  Any other cases?

2) How far about can search and decision be? NP-decision and NP-search they are poly equivalent. In other domains can they be very far apart? For example, is FINDING a k-clique or k-ind set in a graph on 2^{2k} vertices require roughly n^k steps (go through all k-sets) or can we do much better? I suspect this is unknown but would be delighted if a commenter tells me otherwise.



Computational Complexity published first on Computational Complexity