Question about NP problem certificates and P=NP
Your problem is in the black box or oracle setting, that is, you are given access to the input as a black box rather than explicitly. You can contrast your problem with 3SAT, in which the input is a formula. One way to solve 3SAT is to try plugging in solutions at random (or systematically) and checking whether they satisfy the formula. However, better approaches are known, and these approaches use the explicit description of the formula.

The P vs NP question is in the white box setting – concretely, $\mathsf{P} \neq \mathsf{NP}$ is equivalent to the conjecture that no polynomial time algorithm solves 3SAT. Results in black box settings are irrelevant (at least directly) to the P vs NP question.

In the black box model we can also separate P from BPP (at least for promise problems), by considering the problem of finding a zero input for a balanced Boolean function. However, for explicit inputs, it is considered likely that P=BPP. This shows that the black box setting exhibits different behavior than the white box setting.

Black box settings are common in optimization, where often we are looking for algorithms which do not rely on the exact form of the input function. For example, in submodular optimization we are given a submodular function as a black box. One method for proving lower bounds in this area is the indistinguishability method, in which we construct two black boxes which are identical on most inputs but have a very different optimal solution. This method is technically much easier than similar results in the white box setting (for example, in the special case of set coverage functions or cut functions), which rely on PCP theory.