Boolean functions (original question)
Marc LeBrun
mlb at well.com
Thu Jan 4 15:54:41 CET 2001
>=Russ Cox
> It is tempting to guess that a(5) = 33 and
> a(6) = 63.
It'll be interesting to see what it turns out to be! Why that +/- 1 I
wonder? I hope someone's even now writing the computer program to count
them (cleverly optimized as Antti Karttunen suggested).
> Perhaps someone else can see an argument why
> chains of XOR should be the hardest function?
Maybe not a rigorous one.
But as I mentioned before it's certainly a candidate, since every argument
contributes information to the value.
If XOR[n] is one of the hardest then so are all the 2^(n-1)-1 images of it
having arguments swapped with their complements (eg EQV when
n=2). Swapping basically just transposes the "hyper truth table" along one
of its axes.
This family also exhausts the set of all the all-argument dependent
functions, since any other rearrangement of the outputs will cause the
values to be the same for some arguments.
So maybe that does prove it?
Even so, in order to determine the sequence values it remains to find a
construction giving provably minimal-operation expressions for XOR[n].
More information about the SeqFan
mailing list