Python implementation of non-determinism

More details in the gitlab page of the module

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:
                guess.advance()
            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()
G.add_edge(0, 1)
G.add_edge(0, 2)
G.add_edge(1, 2)
G.add_edge(1, 3)


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()
G.add_edge(0, 1)
G.add_edge(1, 2)
G.add_edge(2, 0)
G.add_edge(3, 1)

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