I would calculate the number of functions of 3 variables such that f (x,y,z)=m (g (x,z),h (y,z))

I tried by brute force checking that if $ f:\{0,1\}^3->\{0,1\}$ the number of functions generated by $g,h : \{0,1\}^2->\{0,1\}$ is 192 over 256 total.

I then wanted to compute if the xyz and g,h are in {0,..n-1} but the complexity is tower-like :

Total number of f : $nf=2^{(n^3)} $ Number of decompositions possible : $nd=2^{(n^2)}*n^{(2n^2)}$

The computer would take a few seconds if n=2 but after weeks for n=3 it had a bug, my computer is too slow.

Is there a way besides brute force to find the redundances ? I noted that that $nd/nf $ has a maximum at n=5 but found no way to compute effectively how many different f are generated.

  • $\begingroup$ Does it help to notice that $192$ is $2^6 \times 3$ or $(2^2)^3 \times 3$? $\endgroup$ – Axel Kemper Dec 9 '17 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.