#TodaysNondeterministicAlgorithm solves the subset sum problem: is there a subset of S having sum k? This one shows a standard “design pattern” for nondeterministic algorithms: for each element of the set S, you just guess if you’re taking it or not, then check if you were right.
November 26, 2024 at 10:07 AM
#TodaysNondeterministicAlgorithm solves the subset sum problem: is there a subset of S having sum k? This one shows a standard “design pattern” for nondeterministic algorithms: for each element of the set S, you just guess if you’re taking it or not, then check if you were right.
I’ve released version 3.1.1 of the nondeterminism Python library (as a reminder, you can now “pip install nondeterminism” and much better documentation is available). See #TodaysNondeterministicAlgorithm for a few examples (watch out for the API updates). github.com/aeporreca/no...
GitHub - aeporreca/nondeterminism: A Python library for nondeterministic algorithms
A Python library for nondeterministic algorithms. Contribute to aeporreca/nondeterminism development by creating an account on GitHub.
github.com
December 16, 2024 at 5:07 PM
I’ve released version 3.1.1 of the nondeterminism Python library (as a reminder, you can now “pip install nondeterminism” and much better documentation is available). See #TodaysNondeterministicAlgorithm for a few examples (watch out for the API updates). github.com/aeporreca/no...
Oooh yesss thank you! That’s really interesting and particularly relevant to this #TodaysNondeterministicAlgorithm thing (I’m looking for short, cool algorithms to present later this year at a seminar for master’s student interns, PhD students and colleagues). I see a few interesting examples there!
December 2, 2024 at 8:16 AM
Oooh yesss thank you! That’s really interesting and particularly relevant to this #TodaysNondeterministicAlgorithm thing (I’m looking for short, cool algorithms to present later this year at a seminar for master’s student interns, PhD students and colleagues). I see a few interesting examples there!
#TodaysNondeterministicAlgorithm is Lucky Search! Tired of waiting O(n) time for a linear search? Don’t even have O(log n) time for a binary search? Well, why don’t you just guess where the element is in your array straight on your first try?
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import (
nondeterministic, guess
)
@nondeterministic
def lucky_search(A, x):
n = len(A)
i = guess(range(n))
if A[i] == x:
return i](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreie2rez4exhieipsyc3hiezuifp2m6gzfb24oy5qzhktmnxjv5qrum@jpeg)
![>>> A = [5, 1, 3, 3, 2, 4]
>>> lucky_search(A, 5)
0
>>> lucky_search(A, 3)
2
>>> lucky_search(A, 4)
5
>>> lucky_search(A, 7)
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreihlbosapcqxeqpoq634gunzlpw7ymdtt3fn7xivjbhogszrorafya@jpeg)
November 20, 2024 at 7:39 PM
#TodaysNondeterministicAlgorithm is Lucky Search! Tired of waiting O(n) time for a linear search? Don’t even have O(log n) time for a binary search? Well, why don’t you just guess where the element is in your array straight on your first try?
Shortest paths in graphs are so easy. 😴 OTOH, longest simple paths are NP-hard! #TodaysNondeterministicAlgorithm finds them by using “maximising guesses” (freshly added to the nondeterminism library). You can solve all your OptP problems (complexityzoo.net/Complexity_Z...) this way!
![# https://aeporreca.org/nondeterminism
from nondeterminism import *
@nondeterministic
def longest_path(G):
n = len(G)
V = range(n)
P = []
A = V # available vertices
while A: # P is not maximal
v = guess(A, mode=maximize(len))
P.append(v)
A = [w for w in V if G[v][w] and w not in P]
return P](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreidhszlojbgvtfbnsc36outrndcyflibj76lljsqpvqzodiqvnemru@jpeg)
![G1 = [[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[1, 0, 0, 0]]
G2 = [[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 1, 1, 1]]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreiatf7yxnrp6ovi7tz57mzs2q6ujerk3eb3irv6htqqabk7abracby@jpeg)
![>>> longest_path(G1)
[0, 1, 2, 3]
>>> longest_path(G2)
[2, 3, 0]
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreibuis4sknmivv63qzcartwdrbuhmaihvzyfnsd3x4c2qisisd4uou@jpeg)
December 3, 2024 at 2:40 PM
Shortest paths in graphs are so easy. 😴 OTOH, longest simple paths are NP-hard! #TodaysNondeterministicAlgorithm finds them by using “maximising guesses” (freshly added to the nondeterminism library). You can solve all your OptP problems (complexityzoo.net/Complexity_Z...) this way!
#TodaysNondeterministicAlgorithm is actually 5! The same code (guess & eval a logic formula) can be executed in deterministic (take the first answer), nondeterministic (a *positive* answer), conondeterministic (a negative answer), counting (the positive answers) or majority mode.
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import *
from inspect import signature
def arity(f):
return len(signature(f).parameters)
def guess_n_test(formula):
n = arity(formula)
x = [guess() for i in range(n)]
return formula(*x)
@deterministic
def is_first_satisfiable(formula):
return guess_n_test(formula)
@nondeterministic
def is_satisfiable(formula):
return guess_n_test(formula)
@conondeterministic
def is_tautology(formula):
return guess_n_test(formula)
@counting
def satisfiability(formula):
return guess_n_test(formula)
@majority
def is_majority_satisfiable(formula):
return guess_n_test(formula)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreib6czpwdhjrmvaq4yrtc3zp2hf4mv55aiw3tsg67blz4lnhkwowki@jpeg)
November 28, 2024 at 6:40 AM
#TodaysNondeterministicAlgorithm is actually 5! The same code (guess & eval a logic formula) can be executed in deterministic (take the first answer), nondeterministic (a *positive* answer), conondeterministic (a negative answer), counting (the positive answers) or majority mode.
#TodaysNondeterministicAlgorithm solves the longest common subsequence problem (en.wikipedia.org/wiki/Longest...) which is of interest in bioinformatics (and computational linguistics? and more). This is easy for two (or any fixed no. of) sequences, but NP-hard if the number is variable.
![# https://aeporreca.org/nondeterminism
from nondeterminism import *
def guess_subsequence(s):
t = ''
for c in s:
# take character c?
if guess(mode=maximize(len)):
t += c
return t
def is_subsequence(s, t):
i = 0
for c in s:
# look for c in t[i:]
i = t.find(c, i)
if i == -1:
return False
i += 1
return True
@nondeterministic
def lcs(*sequences):
# take the shortest s for efficiency
s = min(sequences, key=len)
t = guess_subsequence(s)
if all(is_subsequence(t, s)
for s in sequences):
return t](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreid2i67ej25va44zcknguphwmkg7inec4is6qfa3otvuxyggxyd43q@jpeg)
December 6, 2024 at 8:39 AM
#TodaysNondeterministicAlgorithm solves the longest common subsequence problem (en.wikipedia.org/wiki/Longest...) which is of interest in bioinformatics (and computational linguistics? and more). This is easy for two (or any fixed no. of) sequences, but NP-hard if the number is variable.
#TodaysNondeterministicAlgorithm checks if a… nondeterministic finite automaton N (this definition en.wikipedia.org/wiki/Nondete..., without ε moves for simplicity) accepts a string x. Then, by using Python generators, you can lazily construct the whole (possibly infinite) language of N.
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import *
@nondeterministic
def accepts(N, x, q=None):
(Σ, δ, q_0, F) = N # Unpack the NFA
if q is None: # If a state is not given
q = q_0 # ...then use q₀
if x == '': # End of the word
return q in F # Do we accept?
q_1 = guess(δ(q, x[0])) # Guess a transition
return accepts(N, x[1:], q_1) # Recursion on the rest](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreihsc6qcwsskgdbpwibtn3ilogomfkm7wvp3ud7pkcl3m2lebkcl7q@jpeg)
![Python interpreter:
>>> accepts(N, '')
False
>>> accepts(N, '10')
False
>>> accepts(N, '101')
True
>>> accepts(N, '010101101')
True
>>> # Take the first 30 strings in L(N)
>>> list(islice(language(N), 30))
['111', '110', '101', '100', '1111', '1110', '1101', '1100', '0111', '0110', '0101', '0100', '11111', '11110', '11101', '11100', '10111', '10110', '10101', '10100', '01111', '01110', '01101', '01100', '00111', '00110', '00101', '00100', '111111', '111110']
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreigm24axy3qlw2chlvo2f2tks7oynln4zhvjmvb4e2mbx3awdlq3x4@jpeg)
November 30, 2024 at 8:01 AM
#TodaysNondeterministicAlgorithm checks if a… nondeterministic finite automaton N (this definition en.wikipedia.org/wiki/Nondete..., without ε moves for simplicity) accepts a string x. Then, by using Python generators, you can lazily construct the whole (possibly infinite) language of N.
#TodaysNondeterministicAlgorithm shows that you don’t need binary trees to be “search” if you have nondeterminism. Just guess correctly if you need to go left or right! (You still need them balanced though, if you want that sweet O(log n) runtime.)
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import *
from dataclasses import dataclass
type Tree[A] = Node[A] | None
@dataclass
class Node[A]:
key: A
left: Tree[A] = None
right: Tree[A] = None
@nondeterministic
def contains[A](T: Tree[A], k: A) -> bool:
if T is None:
return False
if T.key == k:
return True
if guess(): # Go left?
return contains(T.left, k)
else:
return contains(T.right, k)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreiaxf475knrsc4ptzlvelxjitwhzdasitg2lmrpjcca5hnjs5n2dsa@jpeg)
November 25, 2024 at 6:42 AM
#TodaysNondeterministicAlgorithm shows that you don’t need binary trees to be “search” if you have nondeterminism. Just guess correctly if you need to go left or right! (You still need them balanced though, if you want that sweet O(log n) runtime.)
#TodaysNondeterministicAlgorithm computes spanning trees! Just guess a subgraph and check if it’s a tree! (The is_connected algorithm is chosen for its coolness, not because it’s the most efficient.)
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import *
import numpy as np
def is_connected(G):
n = len(G)
H = sum(G**i for i in range(1, n + 1))
return H.all() # All entries True?
def is_tree(G):
if not is_connected(G):
return False
m = np.count_nonzero(G) // 2 # Number of edges
return m == len(G) - 1
@nondeterministic
def spanning_tree(G):
T = G.copy()
n = len(T)
# Guess some edges to delete
for i in range(n):
for j in range(i + 1, n):
T[i, j] = T[j, i] = T[i, j] and guess()
if is_tree(T):
return T](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreiewgomsiooywojq6x6rm45sf7rvgaxqe7j4my2zdnxibxz2wfdphi@jpeg)
![Python code:
G = np.matrix([[False, True, True, True ],
[True, False, True, False],
[True, True, False, False],
[True, False, False, False]])
H = np.matrix([[False, True, False, False],
[True, False, False, False],
[False, False, False, True ],
[False, False, True, False]])](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreia4jrg6ydnm5cet6ngxwef5a3n6fx4hl4flzlymwqp6qmpqqcxyra@jpeg)
![Python interpreter:
>>> spanning_tree(G)
matrix([[False, False, True, True],
[False, False, True, False],
[ True, True, False, False],
[ True, False, False, False]])
>>> spanning_tree(H)
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreih2gyxtq25rp4xiwhlbpi4ofnhjobn6eznsc3fmaayxb3jb7nqbii@jpeg)
November 27, 2024 at 7:59 AM
#TodaysNondeterministicAlgorithm computes spanning trees! Just guess a subgraph and check if it’s a tree! (The is_connected algorithm is chosen for its coolness, not because it’s the most efficient.)
#TodaysNondeterministicAlgorithm checks if a string is an anagram another! Just guess a permutation of one of them, compare the result with the other, and in at least one possible universe you will get True if and only if it’s indeed an anagram!
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import (
nondeterministic, guess
)
def guess_permutation(s):
n = len(s)
A = list(s)
for i in range(n):
j = guess(range(i, n))
A[i], A[j] = A[j], A[i]
return ''.join(A)
@nondeterministic
def is_anagram(s, t):
u = guess_permutation(t)
return s == u](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreia66hyctd53uz67yzc47pe7hqwb24lbgmc7o6ff5gtyjxlfvfriqe@jpeg)
November 22, 2024 at 8:45 AM
#TodaysNondeterministicAlgorithm checks if a string is an anagram another! Just guess a permutation of one of them, compare the result with the other, and in at least one possible universe you will get True if and only if it’s indeed an anagram!
Shorter version of #TodaysNondeterministicAlgorithm using set comprehensions!
November 26, 2024 at 12:40 PM
Shorter version of #TodaysNondeterministicAlgorithm using set comprehensions!
#TodaysNondeterministicAlgorithm I’ve already published, but it’s Saturday so it’s OK. It’s a SAT solver in 5 lines of Python! The trick is to use a defaultdict (docs.python.org/3/library/co...) for the assignment: the first time you access a variable, its value is guessed automatically.
![Python code:
def φ(x):
return ((not x[0] or not x[1]) and
(x[1] or not x[2]) and
(not x[0] or not x[2]))
def ψ(x):
return x[0] and not x[0]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreiekfecfhl2m2zeyuv4gxqczughoavwtgl4ll4oggeym55q4kxbrbm@jpeg)
November 23, 2024 at 8:17 AM
#TodaysNondeterministicAlgorithm I’ve already published, but it’s Saturday so it’s OK. It’s a SAT solver in 5 lines of Python! The trick is to use a defaultdict (docs.python.org/3/library/co...) for the assignment: the first time you access a variable, its value is guessed automatically.
#TodaysNondeterministicAlgorithm is reachability in directed graphs! This one is better than any known deterministic algorithm in terms of auxiliary space complexity, only O(log n) rather than linear (en.wikipedia.org/wiki/St-conn...)! As a bonus, a version that actually outputs the path.
![Python code:
# http://aeporreca.org/nondeterminism
from nondeterminism import *
@nondeterministic
def is_reachable(G, s, t):
n = len(G)
for i in range(n):
if s == t:
return True
v = guess(range(n))
if G[s][v] != 1:
return False
s = v
return False
@nondeterministic
def path(G, s, t):
n = len(G)
P = [s]
for i in range(n):
if s == t:
return P
v = guess(range(n))
if G[s][v] != 1:
return
s = v
P.append(s)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreicggjocfcsntfhhzsru3p7mlovwhhrfnz5w7jiihvme56txamngtu@jpeg)
![Python code:
G = [[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 1, 0, 0]]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreidmmo25ib4kylhm72na7nebhqdfcf6afeml66liwhrkcwtumh7sfq@jpeg)
![Python interpreter:
>>> is_reachable(G, 0, 0)
True
>>> path(G, 0, 0)
[0]
>>> is_reachable(G, 0, 2)
True
>>> path(G, 0, 2)
[0, 1, 1, 2]
>>> is_reachable(G, 0, 3)
True
>>> path(G, 0, 3)
[0, 1, 2, 3]
>>> is_reachable(G, 2, 0)
False
>>> is_reachable(G, 1, 0)
False
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreib4sd55zssr2fdwiuq2ompdpl4p3nefh4wpatmz4jb6qg5uojf5eu@jpeg)
November 29, 2024 at 9:07 AM
#TodaysNondeterministicAlgorithm is reachability in directed graphs! This one is better than any known deterministic algorithm in terms of auxiliary space complexity, only O(log n) rather than linear (en.wikipedia.org/wiki/St-conn...)! As a bonus, a version that actually outputs the path.
Nondeterminism allows you to write a comparison-based sorting algorithm that only makes n − 1 comparisons, like #TodaysNondeterministicAlgorithm! This is mathematically impossible for a deterministic algorithm, which need Ω(n log n) comparisons (en.wikipedia.org/wiki/Compari...).
![# https://aeporreca.org/nondeterminism
from nondeterminism import *
from itertools import pairwise
@nondeterministic
def lucky_sort(A):
n = len(A)
B = A.copy()
# guess a permutation of B
for i in range(n):
j = guess(range(i, n))
B[i], B[j] = B[j], B[i]
# check if sorted
for i in range(n - 1):
if B[i] > B[i + 1]:
return # give up
return B](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreibqnuirp7zsl7nfxprovx465csvr5txbniy6qhqaarqssns5svux4@jpeg)
![>>> lucky_sort([])
[]
>>> lucky_sort([1, 2, 3])
[1, 2, 3]
>>> lucky_sort([3, 2, 1])
[1, 2, 3]
>>> A = [1, 2, 3, 4, 5]
>>> from random import shuffle
>>> shuffle(A)
>>> A
[1, 3, 5, 2, 4]
>>> lucky_sort(A)
[1, 2, 3, 4, 5]
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreidfjda4a7tkrmwrarml4mt5jhmrl75gmmcvunqmy7lpklbe5ki2nu@jpeg)
December 5, 2024 at 6:36 AM
Nondeterminism allows you to write a comparison-based sorting algorithm that only makes n − 1 comparisons, like #TodaysNondeterministicAlgorithm! This is mathematically impossible for a deterministic algorithm, which need Ω(n log n) comparisons (en.wikipedia.org/wiki/Compari...).
The paper “Which Problems Have Strongly Exponential Complexity?” by Impagliazzo, Paturi and Zane seems to contain all the details I need in order to discuss the number of nondeterministic bits in #TodaysNondeterministicAlgorithm for some NP-complete problems (notably 3SAT vs CLIQUE). 📌
December 4, 2024 at 8:24 AM
The paper “Which Problems Have Strongly Exponential Complexity?” by Impagliazzo, Paturi and Zane seems to contain all the details I need in order to discuss the number of nondeterministic bits in #TodaysNondeterministicAlgorithm for some NP-complete problems (notably 3SAT vs CLIQUE). 📌
#TodaysNondeterministicAlgorithm is one of the examples for the nondeterminism library, but hey, it’s Sunday (and it’s slightly nicer this way). A natural number is composite if it has a proper divisor (≤ √n, if we want to optimise) and a prime is just a non-composite n > 1.
![Python interpreter:
>>> is_prime(0)
False
>>> is_prime(1)
False
>>> is_prime(2)
True
>>> is_prime(3)
True
>>> [n for n in range(200) if is_prime(n)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreia6addsc74ewua4todllky7tygdgv42hjqm7ixhoenv343j7gpuge@jpeg)
November 24, 2024 at 8:13 AM
#TodaysNondeterministicAlgorithm is one of the examples for the nondeterminism library, but hey, it’s Sunday (and it’s slightly nicer this way). A natural number is composite if it has a proper divisor (≤ √n, if we want to optimise) and a prime is just a non-composite n > 1.
#TodaysNondeterministicAlgorithm checks if two graphs are isomorphic, which is hard (but possibly not NP-complete, en.wikipedia.org/wiki/Graph_i...). Two graphs G, H given as adjacency matrices are isomorphic iff there exists a permutation matrix P (which we can guess) such that PG = HP.
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import *
import numpy as np
def guess_perm(S):
P = list(S)
n = len(P)
for i in range(n):
j = guess(range(i, n))
P[i], P[j] = P[j], P[i]
return P
def guess_perm_matrix(n):
M = np.matrix(np.zeros((n, n), dtype=bool))
P = guess_perm(range(n))
for i in range(n):
M[i, P[i]] = True
return M
@nondeterministic
def is_isomorphic(G, H):
n = len(G)
P = guess_perm_matrix(n)
return np.array_equal(P * G, H * P)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreibd45fumpae2loz5noze6553pawb7dysh4onpow453ejt5xbp7gqy@jpeg)
![Python code:
G1 = np.matrix([[False, True, True, True ],
[True, False, True, False],
[True, True, False, False],
[True, False, False, False]])
G2 = np.matrix([[False, False, False, True ],
[False, False, True, True ],
[False, True, False, True ],
[True, True, True, False]])
G3 = np.matrix([[False, False, False, True ],
[False, False, False, True ],
[False, False, False, True ],
[True, True, True, False]])](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreic3ou4pfvjyexg6bfxr6v7dbm3bzrcms5xngksejqwter65knc2xe@jpeg)
December 2, 2024 at 7:57 AM
#TodaysNondeterministicAlgorithm checks if two graphs are isomorphic, which is hard (but possibly not NP-complete, en.wikipedia.org/wiki/Graph_i...). Two graphs G, H given as adjacency matrices are isomorphic iff there exists a permutation matrix P (which we can guess) such that PG = HP.
#TodaysNondeterministicAlgorithm is more powerful than usual (under standard complexity theory assumptions) 💪! We use alternation (en.wikipedia.org/wiki/Alterna...) here, with the standard guess(mode=Or) and conjunctive guess(mode=And) in order to evaluate quantified Boolean formulae!
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import *
from inspect import signature
def arity(function):
return len(signature(function).parameters)
@nondeterministic
def is_qsatisfiable(formula):
n = arity(formula)
x = []
for i in range(n):
if i % 2 == 0:
x.append(guess(mode=Or))
else:
x.append(guess(mode=And))
return formula(*x)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreigaff7m2os7cm7welpblckttqzrkj3jbrlfkrzf6jsgqxazuyx4uy@jpeg)
December 1, 2024 at 6:26 PM
#TodaysNondeterministicAlgorithm is more powerful than usual (under standard complexity theory assumptions) 💪! We use alternation (en.wikipedia.org/wiki/Alterna...) here, with the standard guess(mode=Or) and conjunctive guess(mode=And) in order to evaluate quantified Boolean formulae!
#TodaysNondeterministicAlgorithm is for k-colouring graphs! You just guess a colour for each vertex and then check if connected ones have different colours; if not… you just give up! 🤷♂️ Who cares? Another computation will guess the right colouring! (That is, if it exists!)
![Python code:
# https://aeporreca.org/nondeterminism
from nondeterminism import (
nondeterministic, guess
)
@nondeterministic
def k_color(G, k):
n = len(G)
colors = range(k)
C = [guess(colors)
for i in range(n)]
for u in range(n):
for v in range(n):
if G[u][v] == 1 and C[u] == C[v]:
return
return C](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreigxfmsweth4g3nzbnc3plvnu6m55paqazbgrc5rjkj3m4xzpjvhcy@jpeg)
![Python code for the adjacency matrices of two graphs:
K_3_3 = [[0, 0, 0, 1, 1, 1],
[0, 0, 0, 1, 1, 1],
[0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0]]
K_5 = [[0, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
[1, 1, 0, 1, 1],
[1, 1, 1, 0, 1],
[1, 1, 1, 1, 0]]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreieaqzvl2whwskj4vkoyuiebod6grfmvqtrcqurlgmxgd42zaynruu@jpeg)
![Python interpreter session:
>>> k_color(K_3_3, 1)
>>> k_color(K_3_3, 2)
[0, 0, 0, 1, 1, 1]
>>> k_color(K_5, 1)
>>> k_color(K_5, 2)
>>> k_color(K_5, 3)
>>> k_color(K_5, 4)
>>> k_color(K_5, 5)
[0, 1, 2, 3, 4]
>>>](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreifowxeypkb33zkrkzcki24tooplp5whuf33qqbzndszvthwdefi2e@jpeg)
November 21, 2024 at 2:00 PM
#TodaysNondeterministicAlgorithm is for k-colouring graphs! You just guess a colour for each vertex and then check if connected ones have different colours; if not… you just give up! 🤷♂️ Who cares? Another computation will guess the right colouring! (That is, if it exists!)
This week I’ve inaugurated a #TodaysNondeterministicAlgorithm “column” with Python code on Twitter (x.com/search?q=%23...) and Bluesky (bsky.app/hashtag/Toda...), both for fun and because I need examples for a future seminar talk. There are already 5 entries, with more coming!
November 24, 2024 at 10:49 AM
This week I’ve inaugurated a #TodaysNondeterministicAlgorithm “column” with Python code on Twitter (x.com/search?q=%23...) and Bluesky (bsky.app/hashtag/Toda...), both for fun and because I need examples for a future seminar talk. There are already 5 entries, with more coming!
#TodaysNondeterministicAlgorithm checks if G has a clique (complete subgraph) with size vertices. This is NP-complete but, unlike other NPC problems like 3SAT, you only need √n nondet bits (n = |V²|), which is o(n), while 3SAT needs Ω(n) assuming ETH (en.wikipedia.org/wiki/Exponen...).
![# https://aeporreca.org/nondeterminism
from nondeterminism import *
from itertools import product
@nondeterministic
def has_clique(G, size):
V = range(len(G))
# Guess the clique
C = {v for v in V if guess()}
if len(C) < size:
return False
for v, w in product(C, C):
if v != w and not G[v][w]:
return False
return True](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreight2ruy76xo5gitaukqifpx45c3mv7begmgnjp4ykjnkbq3bwbii@jpeg)
![G = [[0, 1, 0, 1, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 1],
[1, 1, 0, 0, 1],
[1, 1, 1, 1, 0]]
H = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreihukry2rvs6raq6uc3ozpxgt5g2iax5tmf6icmrgb6vt6c747hhey@jpeg)
December 4, 2024 at 11:16 AM
#TodaysNondeterministicAlgorithm checks if G has a clique (complete subgraph) with size vertices. This is NP-complete but, unlike other NPC problems like 3SAT, you only need √n nondet bits (n = |V²|), which is o(n), while 3SAT needs Ω(n) assuming ETH (en.wikipedia.org/wiki/Exponen...).