What's an example of a problem that is in Psearch, but not in NPsearch?

Question

I was told during a lecture that there exist computational problems that are within $\text{P}_\text{search}$ but are not in $\text{NP}_\text{search}$ this seems impossible to me because I feel like a simple verifier is just to run the imaginary solution algorithm on the input, then see if it equals the output. Is there an example of a problem that fits requirements, or a way to construct a set of them?

• D.W.: @AinsleyH. Can I encourage you to write that as an answer rather than a comment, so we can upvote it, it can be accepted, and the question can be treated as answered? No need to write anything more than you already did.

Answer 1

Any deterministic Turing machine is also a nondeterministic Turing machine (but not the other way around).

Hence that claim is false. $^\dagger$

See also the recent answer These classes are called FNP and FP (respectively) in the literature.

---

$^\dagger$ While researching a bit more, I cannot find a formal definition of P_search and NP_search.

Here is a quote from Complexity Zoo on FP:

Sometimes defined as the class of functions computable in polynomial time by a Turing machine. (Generalizes P, which is defined in terms of decision problems only.)

However, if we want to compare FP to FNP, we should instead define it as the class of FNP problems (that is, polynomial-time predicates P(x,y)) for which there exists a polynomial-time algorithm that, given x, outputs any y such that P(x,y). That is, there could be more than one valid output, even though any given algorithm only returns one of them.

I am willing to admit that there might exist a definition of the two classes for which the claim is true.