# Python implementation of non-determinism

It is possible to use python decorators to implement non-determinism.

First some definitions. In theoretical computer science, non-determinism is used to abstract models of computation which are really interesting to capture stratification of some complexity classes.

A non-deterministic Turing machine is allowed to choose along its execution some transitions. See the wikipedia page for a formal description.

Students often struggle to understand how non-determinism works and
often confuse it with randomised algorithms. It is possible to provide a
`Pythonic`

variant of a non-deterministic Turing machine by
allowing the Python program to guess some boolean.

For instance, the following program that can’t actually run:

```
def kclick( V: tuple[int], E: set[tuple[int, int]], k: int) -> bool:
"""
Return True if the input graph contains a k-clique.
See: https://en.wikipedia.org/wiki/Clique_problem
"""
= []
possible_subset for n in V:
if guess():
possible_subset.append(n)for node1 in possible_subset:
for node2 in possible_subset:
if node1 == node2:
continue
if (node1, node2) not in E and (node2, node1) not in E:
return False
return len(possible_subset) => k
```

Such a function evaluates to `True`

if and only if there
exists a sequence of guesses such that the final result is
`True`

. Otherwise the final result is `False`

.

It is actually possible to rely on high order construction in Python to design a non-deterministic execution of functions.

First we need a class that allows exploring the space of guesses
efficiently. To do that, we just need to choose a way to explore the
binary tree of those guesses, starting with the branch with only
`False`

and ending with the one with only
`True`

.

We can implement this through a simple class:

```
class Guesser:
def __init__(self) -> None:
self.branch: list[bool] = []
self.position: int = 0
def __call__(self) -> bool:
if self.position >= len(self.branch):
self.branch.append(False)
self.position += 1
return self.branch[self.position - 1]
def next(self) -> bool:
self.branch = self.branch[: self.position+1]
if all(self.branch):
return False
for i in range(len(self.branch), 0, -1):
if not self.branch[i - 1]:
self.branch[i - 1] = True
break
self.branch[i - 1] = False
self.position = 0
return True
```

With that, we can implement a nice decorator.

```
from functools import wraps
def nondet(fct, verbose=False):
= nondet_iter(fct, verbose=verbose)
fct_iter
@wraps(fct)
def _fct(*args, **kwargs):
try:
return next(fct_iter(*args, **kwargs))
except StopIteration:
return None
return _fct
def nondet_iter(fct, verbose=False):
@wraps(fct)
def _fct(*args, **kwargs):
= Guesser()
guess while True:
if verbose:
guess.advance()= fct(guess, *args, **kwargs)
res if res is not None:
yield res
if not guess.next():
return res
return _fct
```

And now, we can actually run our non-deterministic program:

```
import networkx as nx
@nondet
def kclique(guess, G: nx.Graph, k: int) -> list | None:
"""
Return a k-clique if the input graph contains a k-clique and False otherwise
See: https://en.wikipedia.org/wiki/Clique_problem
"""
= list()
possible_subset for node in G:
if guess():
for node2 in possible_subset:
if (node, node2) not in G.edges:
return None
possible_subset.append(node)
if len(possible_subset) == k:
return possible_subset
return None
= nx.Graph()
G 0, 1)
G.add_edge(0, 2)
G.add_edge(1, 2)
G.add_edge(1, 3)
G.add_edge(
print(kclique(G, 3))
```

`[0, 1, 2]`

We can also give a negative example:

`print(kclique(G, 4))`

`None`

Of course, it is not really efficient but it makes non-determinism a bit more concrete.

We can of course change the setup a little to handle non-boolean
output. By taking the convention that the function is successful if the
result evaluates to `False`

, we can rewrite the decorator as
follows:

```
def nondet(fct):
@wraps(fct)
def _fct(*args, **kwargs):
= Guesser()
guess while True:
= fct(guess, *args, **kwargs)
res if res:
return res
if not guess.next():
return res
return _fct
```

Now we can find the actual clique:

```
@nondet
def kclique(guess, G: nx.Graph, k: int) -> list[int] | None:
"""
Return a k-clicque if it exists and None otherwise
See: https://en.wikipedia.org/wiki/Clique_problem
"""
= []
possible_subset for n in G:
if guess():
possible_subset.append(n)
for node1, node2 in zip(possible_subset, possible_subset[1:]):
if (node1, node2) not in G.edges:
return None
if len(possible_subset) >= k:
return possible_subset[:k]
= nx.Graph()
G 0, 1)
G.add_edge(1, 2)
G.add_edge(2, 0)
G.add_edge(3, 1)
G.add_edge(
print(kclique(G, 3))
```

`[0, 1, 3]`

We can also find a 3-coloration:

```
from typing import Literal
= Literal[0] | Literal[1] | Literal[2]
colors
@nondet
def three_col(guess, G: nx.Graph) -> dict[int, colors] | Literal[False]:
"""
Return a 3 coloration of the input graph if it exists and False otherwise
See: https://en.wikipedia.org/wiki/Graph_coloring#Properties
"""
= dict()
coloring for n in G:
if guess():
= 0
coloring[n] elif guess():
= 1
coloring[n] else:
= 2
coloring[n]
for x,y in G.edges:
if coloring[x] == coloring[y]:
return None
return coloring
print(three_col(G))
```

`{0: 2, 1: 1, 2: 0, 3: 2}`

Compiled the: jeu. 01 févr. 2024 17:40:01 CET