I wonder who needs to know this who doesn’t also need to know the difference between a decision (yes/no) problem and a general problem. This is relevant because P and NP are only defined for decision problems, but all of the examples given aren’t such problems.
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.
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”.
