4

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.

Pranav Sodhani
  • 115
  • 13
  • I'm voting to close this question as off-topic because this question is better suited for CS Stack Exchange! – Am_I_Helpful Oct 23 '16 at 20:39
  • https://en.wikipedia.org/wiki/Las_Vegas_algorithm – Mooing Duck Oct 23 '16 at 20:43
  • What does recognizing a language mean in your context? – Nico Schertler Oct 23 '16 at 21:44
  • That is if I give an input to the algorithm, it can tell me if the given input belongs to the language or not. (all in the context of decision problems.) – Pranav Sodhani Oct 23 '16 at 22:00
  • Possible duplicate of [What are the consequences of saying a non-deterministic Turing Machine can solve NP in polynomial time?](http://stackoverflow.com/questions/3713293/what-are-the-consequences-of-saying-a-non-deterministic-turing-machine-can-solve) – Matt Timmermans Oct 24 '16 at 00:18
  • It is not coin flipping. Any time a non-deterministic computer needs faces a condition, it forks itself, and takes both branches simultaneously. – user58697 Oct 24 '16 at 02:27
  • My concern is how can it do it in polynomial time if it takes both branches? – Pranav Sodhani Oct 24 '16 at 02:38

2 Answers2

6

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

A. Mashreghi
  • 1,729
  • 2
  • 20
  • 33
0

Non-determinism in this case refers to the ability of the computational model to, in some technical sense, "guess" the right (execution) path from among all possible execution paths. A. Mashreghi describes it nicely in his answer.

An equivalent way of characterizing NP is that it is comprised of those problems for which, given an instance I of the problem and a "certificate" C(I) (of which you can think of as a hint to the algorithm), we can verify whether the instnace has a solution in time polynomial in the size of the instance and the size of the certificate. (There is a formal proof of equivalence between these two characterizations. See, for example, the book by Arora and Barak.)

blazs
  • 4,705
  • 24
  • 38