[thelastquestion]

They can always be reduced, but sometimes with an unacceptably large (e.g., non-polynomial) increase in time complexity.

These are the complexity classes of Function P (FP) and Function NP (FNP), which are the function problem extensions of the decision problem classes, and require finding the value, not just answering yes or no.

A simple example of a decision problem in P but whose search problem is not known to be in FP: For a given integer x, “does there exist a non-trivial prime factor of x?” vs. “find a non-trivial prime factor of x”.