 This is an example of a so-called decision problem. The answer is a simple “yes” or “no”, but it might be hard to find the answer. Observe that the formulation of the question conditional to S has descriptive complexity \(\log k + c\), whereas most random subsets of S have a conditional descriptive complexity of \(|S|\). So any subset \(S^{\prime}\) that adds up to k might have a descriptive complexity that is bigger then the formulation of the search problem. In this sense search seems to generate information. The problem is that if such a set exists the search process is bounded, and thus effective, which means that the phrase “the first subset of S that adds up to k” is an adequate description. If \(\textrm{P} = \textrm{NP}\) then the Kolmogorov complexity and the Levin complexity of the set \(S^{\prime}\) we find roughly coincide, if \(P \neq \textit{NP}\) then in some cases \(Kt(S^{\prime}) \gg K(S^{\prime})\). Both positions, the theory that search generates new information and the theory that it does not, are counterintuitive from different perspectives.