The algorithms we use to solve programming tasks are deterministic. This means that at any given time the evolution of the algorithm is uniquely determined, and is specified by the instruction to be executed in a particular moment. There is another category of algorithms, however, which bring a great theoretical value. Non-deterministic algorithms are not directly applicable, but their study raises some important concepts.
The definition for the correctness of non-deterministic algorithms is the first surprising aspect about these. Such an algorithm is correct if there is a possibility that it finds the right answer after its execution. Take a look at the following example of a non-deterministic algorithm that searches for the exit in a maze:
exit (current_position) ->
if (there is no wall to the north)
current_position = north of current_position;
or if (there is no wall to the south)
current_position = south of current_position;
or if (there is no wall to the east)
current_position = east of current_position;
or if (there is no wall to the west)
current_position = west of current_position;
Briefly, the algorithm behaves like this: if there is no wall to the north go north, or maybe if there is no wall to the south move south and the same for east, or west. What makes it non-deterministic is that the direction of movement is not specified. It is clear that if there’s an exit and it can be reached, there is a suite of applications of these rules that leads to the exit.
The practical utility of such an algorithm is not immediately apparent and it is clear that such algorithms cannot be directly implemented on a programmable machine. In reality, however, the existence of non-deterministic algorithms shows us that a problem can be solved algorithmically.
Secondly, one can show that any deterministic algorithm can be transformed into a deterministic one automatically. Once we know how to solve a problem in a deterministic way, we can solve it deterministically too! The transformation is relatively simple. For the example above, this would mean trying every direction step by step. This is often known as “flood fill”.
The class of all problems that can be solved by non-deterministic algorithms in polynomial time is denoted by NP (non-deterministic polynomial). It is clear that any problem that is in P is also in NP, because non-deterministic algorithms are only an extreme case of the deterministic ones. On the other hand, it is thought NP problems are not solvable in polynomial time. This is one of the most important debates in modern computer science, as it is still unclear whether the P complexity class is different from NP. What we do know for sure that for every NP problem we can write a program that runs in polynomial time that can check whether the solution produced by a non-deterministic algorithm is actually correct.