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):
        self.current_run = []
        self.position = 0

    def __call__(self):
        if self.position >= len(self.current_run):
            self.current_run.append(False)

        result = self.current_run[self.position]
        self.position += 1
        return result


    def next(self):
        self.current_run = self.current_run[:self.position+1]
        if all(self.current_run):
            return False
        C = self.current_run[::-1]
        for i, e in enumerate(C):
            if not e:
                self.current_run[-i-1] = True
                break
            else:
                self.current_run[-i-1] = False
        self.position = 0
        return True

With that, we can implement a nice decorator.

from functools import wraps

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

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

@choose
def kclique(guess, 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

print(kclique([0, 1, 2, 3], set(((0, 1), (1, 2), (2, 0), (3, 1))), 3))

True

We can also give a negative example:

print(kclique([0, 1, 2, 3, 4], [(0, 1), (1, 2), (2, 3), (4, 0), (4, 2)], 3))

False

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 choose(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:

@choose
def kclique(guess, V: tuple[int], E: set[tuple[int, int]], 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 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
    if len(possible_subset) >= k:
        return possible_subset

print(kclique([0, 1, 2, 3], set(((0, 1), (1, 2), (2, 0), (3, 1))), 3))

[0, 1, 2]

We can also find a 3-coloration:

from typing import Literal

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

@choose
def three_col(guess, V: tuple[int], E: set[tuple[int, int]]) -> 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 V:
        if guess():
            coloring[n] = 0
        elif guess():
            coloring[n] = 1
        else:
            coloring[n] = 2

    for x,y in E:
        if coloring[x] == coloring[y]:
            return False
    return coloring 

print(three_col([0, 1, 2, 3], set(((0, 1), (1, 2), (2, 0), (3, 1)))))

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