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):
fct_iter = nondet_iter(fct, verbose=verbose)

@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):
guess = Guesser()
while True:
if verbose:
res = fct(guess, *args, **kwargs)
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

"""
possible_subset = list()
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

G = nx.Graph()

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):
guess = Guesser()
while True:
res = fct(guess, *args, **kwargs)
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]

G = nx.Graph()

print(kclique(G, 3))
[0, 1, 3]

We can also find a 3-coloration:

from typing import Literal

colors = Literal[0] | Literal[1] | Literal[2]

@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
"""

coloring = dict()
for n in G:
if guess():
coloring[n] = 0
elif guess():
coloring[n] = 1
else:
coloring[n] = 2

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