What is an example of a search problem that is not in NP? I feel like there should be an easy example, but I can't think of one. So, specifically, I am looking for a Yes/No search problem that is not in the class NP. When you learn about P and NP, you get a lot of examples of problems in P, NP, NP-hard, NP-complete, co-NP, etc. I guess, halting problem would work, but I would like something for which computability is not the reason why it is not NP.
 A: You can use the time hierarchy theorem to manufacture problems that have yes/no answers but which aren’t in NP by, say, requiring they take at least a super-polynomial amount of nondeterministic time to compute.
Another option is to look at NEXP-complete problems. The time hierarchy theorem guarantees that none of these problems are solvable in nondeterministic polynomial time, yet they’re all yes/no problems.
A: Actually, no such problem exists! We know this because the way we define the class NP is essentially as the class of all search problems. Remember that any search problem can be defined by an input instance I, and a verification algorithm C, where C(I) returns true if and only if I satisfies whatever constraints we want. C must do this in polynomial time. In the case of the Traveling Salesman Decision problem, C check that our instance I (a path in a graph) is a cycle, touches all vertices exactly once, and has weight less than some budget b. So, even though all problems in NP don't seem like search problems at first, they are. We know this because for all problems in NP, we can solve them via an exhaustive search (iterating through all possible valid inputs to C and seeing if any return True). 
