What is meant by "solvable by non deterministic algorithm in polynomial time"

Problem Detail: 

In many textbooks NP problems are defined as:

Set of all decision problems solvable by non deterministic algorithms in polynomial time

I couldn't understand the part "solvable by non deterministic algorithms". Could anyone please explain that?

Asked By : user5507

Answered By : Dave Clarke

Adding to Shitikanth's answer, a nondeterministic algorithm is one that has multiple choices in some points during its control flow. The actual choice made when the program runs is not determined by the input or values in registers, or if we are talking about Turing machines, the choice is not determined by the input value and the state; instead an arbitrary choice among the possibilities can be made in a given run of the program. Thus multiple runs of the same algorithm on the same input can result in different outputs.

The point of using a non-deterministic algorithm is that it can make certain guesses at certain points during its computation. Such algorithms are designed so that if they make the right guesses at all the choice points, then they can solve the problem at hand.

A simple example is primality testing. To decide whether a number $N$ is not prime, one simply selects non-deterministically a number $n\le\sqrt{N}$ and checks whether $N$ is divisible by $n$. For any composite number, this algorithm finds a factor of the number by making the right guess.

The polynomial time part means that if the nondeterministic algorithm makes all the right guesses, then the amount of time it takes is bounded by a polynomial.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1243