Antonio E. Porreca 🐳
@aeporreca.org
Maître de conférences (lecturer) at https://univ-amu.fr & researcher at https://lis-lab.fr 🐗🇫🇷 • Natural computing, discrete dynamical systems & complexity • Down with generative AI • I like (human) languages • This is a pandemic, y’all 😷 • aeporreca.org
Rare image de Château Gumbear à Marseille.
December 9, 2025 at 12:26 PM
Rare image de Château Gumbear à Marseille.
Voici le communiqué de l’intersyndicale AMU sur la « grande enquête étudiante » de Berton.
December 5, 2025 at 11:53 AM
Voici le communiqué de l’intersyndicale AMU sur la « grande enquête étudiante » de Berton.
Me pretending to be able to play drums.
November 18, 2025 at 12:13 PM
Me pretending to be able to play drums.
Apparently we all missed this particular 2024 journal paper. (This is the “corollary” of a “theorem” which happens to be false.)
June 5, 2025 at 10:49 AM
Apparently we all missed this particular 2024 journal paper. (This is the “corollary” of a “theorem” which happens to be false.)
I had somehow missed until now the paper “Nondeterministic algorithms” by Robert W. Floyd, 1967, which includes nice flowchart algorithms for the 8 queens problem and for finding cycles in a graph, as well as a “determinising” compiler. dl.acm.org/doi/pdf/10.1...
April 29, 2025 at 2:13 PM
I had somehow missed until now the paper “Nondeterministic algorithms” by Robert W. Floyd, 1967, which includes nice flowchart algorithms for the 8 queens problem and for finding cycles in a graph, as well as a “determinising” compiler. dl.acm.org/doi/pdf/10.1...
Cante uno chato de Prouvènço
April 22, 2025 at 10:32 AM
Cante uno chato de Prouvènço
My colleague’s kid drew dinosaurs for me, so it’s only fair I also draw one to reciprocate. 🦕
April 3, 2025 at 12:13 PM
My colleague’s kid drew dinosaurs for me, so it’s only fair I also draw one to reciprocate. 🦕
Écoutez-moi un moment maintenant.
Ça a toujours été sous nos yeux, depuis 1993 !
David Duchovny
David DuchOVNY
David Duch-OVNI
Ça a toujours été sous nos yeux, depuis 1993 !
David Duchovny
David DuchOVNY
David Duch-OVNI
February 18, 2025 at 5:27 PM
Écoutez-moi un moment maintenant.
Ça a toujours été sous nos yeux, depuis 1993 !
David Duchovny
David DuchOVNY
David Duch-OVNI
Ça a toujours été sous nos yeux, depuis 1993 !
David Duchovny
David DuchOVNY
David Duch-OVNI
I love apparently random Italian words in Arabic.
![A Wiktionary page:
بروفا
South Levantine Arabic
Etymology
From Italian prova.
Pronunciation
IPA(key): /broː.va/, [ˈbroː.va]
Audio (al-Lidd):
Noun
بروفا • (brōva) f (plural بروفات (brōvāt))
rehearsal](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreify25wnarr33zyftffbrd5tgas7jqq4q65suq2waawlevkfkx5uwa@jpeg)
February 7, 2025 at 8:42 AM
I love apparently random Italian words in Arabic.
Maltese is unbelievable. Look at this stunning sentence with that Arabic syntax and that vocabulary of mixed Italian (or Sicilian) and Arabic origin. Just amazing. (From youtu.be/s1DyDRn4_Fw)
January 18, 2025 at 8:22 PM
Maltese is unbelievable. Look at this stunning sentence with that Arabic syntax and that vocabulary of mixed Italian (or Sicilian) and Arabic origin. Just amazing. (From youtu.be/s1DyDRn4_Fw)
Love the recursive title, I’m certainly going to publish in this nice journal!
January 8, 2025 at 3:45 PM
Love the recursive title, I’m certainly going to publish in this nice journal!
Anki reminds me that 1000 days ago I resumed studying languages (after a one-year sabbatical).
January 7, 2025 at 2:38 PM
Anki reminds me that 1000 days ago I resumed studying languages (after a one-year sabbatical).
Still working on my French person impression.
December 24, 2024 at 4:54 PM
Still working on my French person impression.
This is a great example of bad user interface: here it appears that the “Feels Like” indicator is a slider that you can adjust, but I assure you it’s read-only! And I bet that in order to unlock it you must modify some obscure configuration file, or buy an alternative 10 $ app.
December 20, 2024 at 10:21 AM
This is a great example of bad user interface: here it appears that the “Feels Like” indicator is a slider that you can adjust, but I assure you it’s read-only! And I bet that in order to unlock it you must modify some obscure configuration file, or buy an alternative 10 $ app.
An old picture of mine, taken during a trip to Gibraltar when I was a visiting PhD student in Sevilla 🇪🇸 in 2011 (damn, that’s so long ago…). The monkey decided autonomously to jump on my shoulder, I did nothing to lure him there. 😊
December 6, 2024 at 9:16 PM
An old picture of mine, taken during a trip to Gibraltar when I was a visiting PhD student in Sevilla 🇪🇸 in 2011 (damn, that’s so long ago…). The monkey decided autonomously to jump on my shoulder, I did nothing to lure him there. 😊
#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.
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...).
#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...).
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 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!
I’ve finally understood how to implement alternation in my nondeterminism Python library. 😊 It would be used more or less like in this example; here “mode” is a class with a method implementing the evaluation for that type of nondeterminism, so it’s fully extensible.
![Python code:
from nondeterminism import *
@nondeterministic
def is_qsatisfiable(formula):
n = nvars(formula)
x = [False for i in range(n)]
for i in range(n):
if i % 2 == 0:
x[i] = guess(mode=Or)
else:
x[i] = guess(mode=And)
return formula(*x)](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:7bcjnl2b5ko25d5zgdpiqgop/bafkreig2gikyvqv4w4ikeiho773lbt3pdmd75hqbbiy7jvov3zpsp2rrpm@jpeg)
December 1, 2024 at 11:04 AM
I’ve finally understood how to implement alternation in my nondeterminism Python library. 😊 It would be used more or less like in this example; here “mode” is a class with a method implementing the evaluation for that type of nondeterminism, so it’s fully extensible.