224
P. Kerntopf et al.
The above listed PPRM expressions show some regular features. However, our
experience is so that extrapolation of such features of PPRMs is very difficult
because: (1) usually a component function is obtained which is not balanced,
(2) even if all PPRMs correspond to balanced functions, then their collection
does not constitute a reversible function. Therefore we have decided to apply
extrapolation based on cycle structures. By considering the appropriate mappings
{0, 1} 3 → {0, 1} 3 it is easy to establish that the above three representatives have the
following cycle structures (note that here and later on we use the reverse order of
variables and component functions and instead of a 3-tuple of binary values (a 3 , a 2 ,
a 1 ) or (c, b, a) we use its decimal equivalent):
The representative of the NPNP class R28: < 0 > < 4 > < 1, 7, 2, 6, 3, 5 >,
The representative of the NPNP class R29: < 0 > < 4 > < 5 > < 1, 7, 2, 6, 3 >,
The representative of the NPNP class R32: < 0 > < 2 > < 4 > < 1, 7, 6 > < 3, 5 >.
However, these cycle structures do not help in formulating conjectures for n > 3.
How to get similar results for n = 4 as checking all NPNP classes of 4-variable
reversible functions is not possible because of their enormous number?
In [6] we calculated all NPN classes of balanced 4-variable functions (presented
in Table 1 of [6]). Then we have performed a computational experiment reported in
[6]. Let us quote:
We have checked that only for the following 18 out of 58 NPN-equivalence classes of
balanced Boolean functions up to 4 variables (B1.1, B2.1, B3.1-B3.4, B4.1-B4.52) it is
not possible to find four functions belonging to the same class which would constitute a 4variable reversible function: B2.1, B3.2, B4.2, B4.3, B4.4, B4.7 (this class includes only 2
functions), B4.13, B4.15, B4.27, B4.28, B.4.31, B4.33, B4.34, B4.35, B4.38, B4.42, B4.48,
B4.51.
Later we found a single representative for each of the NPNP-classes of 4-variable
functions which consists of four non-degenerate component functions from the same
NPN class of 4-variable balanced functions. Then we have checked that among 52
NPN-equivalence classes of 4-variable balanced functions (Table 1 of [6]) there are
10 classes having at least one linear variable: B4.1, 4.2, B4.3, B4.4, B4.7, B4.8,
B4.9, B4.13, B4.15, B4.17. Only four of them lead to RevFunCFLVs depending on
all four variables. They are listed below in the same manner as previously 3-variable
RevFunCFLVs.
NPNP Class Built of Balanced Functions from Class B4.1 (Cardinality = 64)
A = a ⊕ bcd (the set of linear variables = {a})
B = b ⊕ ac ⊕ acd (the set of linear variables = {b})
P. Kerntopf et al.
The above listed PPRM expressions show some regular features. However, our
experience is so that extrapolation of such features of PPRMs is very difficult
because: (1) usually a component function is obtained which is not balanced,
(2) even if all PPRMs correspond to balanced functions, then their collection
does not constitute a reversible function. Therefore we have decided to apply
extrapolation based on cycle structures. By considering the appropriate mappings
{0, 1} 3 → {0, 1} 3 it is easy to establish that the above three representatives have the
following cycle structures (note that here and later on we use the reverse order of
variables and component functions and instead of a 3-tuple of binary values (a 3 , a 2 ,
a 1 ) or (c, b, a) we use its decimal equivalent):
The representative of the NPNP class R28: < 0 > < 4 > < 1, 7, 2, 6, 3, 5 >,
The representative of the NPNP class R29: < 0 > < 4 > < 5 > < 1, 7, 2, 6, 3 >,
The representative of the NPNP class R32: < 0 > < 2 > < 4 > < 1, 7, 6 > < 3, 5 >.
However, these cycle structures do not help in formulating conjectures for n > 3.
How to get similar results for n = 4 as checking all NPNP classes of 4-variable
reversible functions is not possible because of their enormous number?
In [6] we calculated all NPN classes of balanced 4-variable functions (presented
in Table 1 of [6]). Then we have performed a computational experiment reported in
[6]. Let us quote:
We have checked that only for the following 18 out of 58 NPN-equivalence classes of
balanced Boolean functions up to 4 variables (B1.1, B2.1, B3.1-B3.4, B4.1-B4.52) it is
not possible to find four functions belonging to the same class which would constitute a 4variable reversible function: B2.1, B3.2, B4.2, B4.3, B4.4, B4.7 (this class includes only 2
functions), B4.13, B4.15, B4.27, B4.28, B.4.31, B4.33, B4.34, B4.35, B4.38, B4.42, B4.48,
B4.51.
Later we found a single representative for each of the NPNP-classes of 4-variable
functions which consists of four non-degenerate component functions from the same
NPN class of 4-variable balanced functions. Then we have checked that among 52
NPN-equivalence classes of 4-variable balanced functions (Table 1 of [6]) there are
10 classes having at least one linear variable: B4.1, 4.2, B4.3, B4.4, B4.7, B4.8,
B4.9, B4.13, B4.15, B4.17. Only four of them lead to RevFunCFLVs depending on
all four variables. They are listed below in the same manner as previously 3-variable
RevFunCFLVs.
NPNP Class Built of Balanced Functions from Class B4.1 (Cardinality = 64)
A = a ⊕ bcd (the set of linear variables = {a})
B = b ⊕ ac ⊕ acd (the set of linear variables = {b})