NP - Non deterministic polynomial time

Question

I have seen multiple definitions of NP and I am a little confused calling it as non-deterministic polynomial time.

"NP is the set of languages that can be recognized in non-deterministic polynomial time."

What I understand is that a regular computer (with no randomness) cannot recognize the language in polynomial time but a computer which has some form of non-determinism (coin flips?) can solve that in polynomial time?

Can someone correct me on this? Can you provide me an example where coin flipping actually solves the problem in polynomial time which would have been exponential otherwise?

I do understand the definition that NP includes languages which can be verified in polynomial time but I don't get how can they be recognized using non-determinism.

Answer 1

In fact, coin flip is about randomness and some people mistakenly describe non-determinism with randomness. Let’s say you have the following problem:

There are n doors, and behind one of them there is prize that you want to find. Now, let’s analyze different approaches:

(Note that in order to simplify the description I don’t use asymptotic notations such as big O)

Deterministic: An example of a deterministic algorithm could be opening all doors from left to right one by one; hence, worst case complexity of n operations

Randomized: I flip a coin, if I got tail I will start checking doors from left to right and if I got head I check them right to left. So, in the expected sense I will get n/2 operations. (Exercise: why?) And in randomized algorithms we look for a good average (expected) behaviour

Nondeterministic: Nondeterminism is a completely different story, which is not possible in the real world. If you have the power of nondeterminism, when faced with multiple choices you can try all of them simultaneously. So, a nondeterministic algorithm can open all n doors at the same time; hence 1 operations to find the prize.

Now, an example of something that can be solved polynomially using nondeterminism. Let’s say you are faced with 2 doors (at depth 1), you choose one and you again see 2 doors (at depth 2) and so on until depth n. So in fact, there are 2^n doors at the last depth, behind one of which there is a prize.

Finding a prize using a deterministic approach takes 2^n operations. However, using non-determinism you can open both doors at depth one simultaneously, open the four doors at level 2 simultaneously, and so on. So, you can find the prized after n (nondeterministic) operations