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

Question

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?

Answer 1

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.

Answer 2

"$L$ is solvable by non deterministic algorithms in polynomial time" means that there exists a non-deterministic turing machine $M$, and a polynomial $p$ s.t. for all $x \in L$, $M$ accepts $x$ in at most $p(|x|)$ steps in one of the branches of its execution.

Answer 3

Informally, the main difference between nondeterministic algorithms and the normal, deterministic, algorithms is that when provided with multiple choices to take, the deterministic solution will have to check one of them at a time in sequence while the nondeterministic version can cheat a bit. There are two main ways to look at it that I know of:

1. When faced with multiple possibilities, the nondeterministic version runs all of them in parallel, suceeding if any of the threads succeed and failing if all of them fail.

2. When faced with multiple possibilities, the nondeterministic version always luckily chooses a possibility that succeeds and fails otherwise.

There is also a popular definition of NP that turns out to be equivalent if you think about it:

A problem is in NP iff it is always possible to provide a polynomially long proof certificate for any positive solution to a problem instance.

---

For a concrete example, let's take the problem of determining if a number $N$ is composite (not prime). A way to solve this is to test all numbers less then N to check whether they are divisors of N.

If you do the tests sequentially this naive algorithm would take exponential time (since $N$ is exponentially large compared to the number of digits it has), but if you are allowed to do a magical nondeterministic choice the algorithm takes polynomial time (since each different divisor test takes polynomial time). Thus, testing if a number is composite is in NP.

And in the alternate formulation, providing a divisor of $N$ gives a polynomially long proof of compositeness.

Answer 4

Here is an equivalent and more natural interpretation:

A problem $L$ is said to be in $NP$ if there is a deterministic polynomial-time algorithm for all $x\in L$ which verifies the membership of $x$ in $L$ using a short certificate $y$ ($|y| \lt |x|^c$).

Answer 5

A non-deterministic algorithm is one where the input includes a random choice. Meaning, the input is composed of the nominal input plus a purely random selection -- so the answers differ when you run the algorithm with the same nominal input time and again. If one of the random choices leads to an easy, short (polynomial) solution, the algorithm is NP (non-deterministic polynomial). The unresolved question (is P=NP?) comes down to: is there anyway to make the random choices non-random, but based on some mathematical smarts. Most mathematicians think that the random choice cannot be "improved" to insure a fast solution, namely they believe that NP problems are immunized against future insight that would solve them in short (polynomial) time. They say: P < NP; or at least claim so in order to give credence to a host of cryptographic products. Alas, even if in general P < NP there are numerous special cases where the solution is fast, so the crypto products that rely on them are vulnerable to advanced math (like the Enigma that was defeated by Alan Turing -- we don't know how many Alan Turings work for our adversaries).