In some case non-deterministic is more efficient, however, if your "hint", or oracle is wrong, you gain no information. Say, factorizing a large number, you make a guess, what the factors are, you then verify your guess. If it is right, you are done, however, if it is wrong, the only thing you know is that you guess is wrong. You cannot say if the number is a prime.

It is like conducting a scientific research, you think of an approach that might work, that is non-deterministic, it is hard to come up with that. One you come up with an approach, follow through. Well, if it doesn't work, you may just end up at the square one.

If it is deterministic, that is different, because you will have a definite answer either way.