What does "nondeterministic" mean in NP?
The nondeterminism captures the ability of a hypothetical nondeterministic machine to "guess" a witness (if one exists) and then verify it deterministically.