NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution
Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression true, it here are any). Thus the cost of the search problem isn't "too much more" (multiply by the size of the input --number of variables-- is polynomial).