the nondeterministic-machine definition of NP

There is a second, equivalent way to define NP, and it is the source of the letter N. Imagine you are at a maze and, instead of walking it carefully, you magically clone yourself at every fork so that all paths are explored at once; if ANY clone reaches the exit, you count it as solved. This is the same nondeterminism you met with the NFA, where the machine could be in several states at once. NP is what you get when you let a nondeterministic machine run, but only for polynomial time.

Formally, a problem is in NP if there is a nondeterministic Turing machine that decides it in polynomial time. Such a machine works in two phases that you can read as guess-then-check. In the GUESS phase it writes down a string nondeterministically, conceptually trying every possible string in parallel; this guessed string is exactly the certificate. In the CHECK phase it runs deterministically to verify the guess, in polynomial time. The machine accepts the input if there EXISTS some guess that leads to acceptance. 'Exists an accepting path' is the same 'exists a certificate' as the verifier definition, which is why the two definitions describe the very same class.

Translating between the two views is mechanical and worth internalising. A verifier plus a guessed certificate is a nondeterministic machine; a nondeterministic machine's lucky sequence of choices is a certificate. The guessing is a mathematical fiction, not real hardware, exactly as with the NFA: we are not claiming a computer can magically clone itself. It is a clean way to define 'a short certificate exists'. The stakes are simply higher than for finite automata. For an NFA, nondeterminism cost nothing in power; here, whether nondeterministic polynomial time is truly more powerful than deterministic polynomial time is precisely the open P versus NP question.