The effect of null-chains on the complexity of contact schemes. (English) Zbl 0728.94012

Jukna, Stasys P.

Fundamentals of computation theory, Proc. Int. Conf., FCT ’89, Szeged/Hung. 1989, Lect. Notes Comput. Sci. 380, 246-256 (1989).

Summary: [For the entire collection see Zbl 0726.00019.]
The contact scheme complexity of Boolean functions has been studied for a long time but its main problem remains unsolved: we have no example of a simple function (say in NP) that requires \(\Omega (n^ 3)\) contact scheme size. The reason is, perhaps, that although the contact scheme model is elegantly simple, our understanding of the way it computes is vague.
On the other hand, it is known that the main tool to reduce the size of schemes is to use “null-chains”, i.e. chains with zero conductivity. (These chains enable one to merge nonisomorphic subschemes). So, in order to better understand the power of this tool, it is desirable to have lower bound arguments for schemes with various restrictions on null- chains.
In this report such arguments are described for schemes without null- chains, for schemes with restricted topology of null-chains, and for schemes with restricted number and/or restricted length of null-chains. In all these cases nearly-exponential lower bounds are established. Finally, we prove that null-chains do not help at all if schemes are required to realize sufficiently many prime implicants.

MSC:

94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25	Analysis of algorithms and problem complexity

Keywords:

contact scheme complexity of Boolean functions; null-chains; lower bounds; prime implicants

Citations:

Zbl 0726.00019