A. V. Galatenko, V. A. Nosov, A. E. Pankratiev, V. M. Staroverov, “Generation of proper families of functions”, Intelligent systems. Theory and applications, 2021, Volume 25, Issue 4,Pages <nobr>100

Part 2. Mathematics and Computer Science

Generation of proper families of functions

A. V. Galatenko, V. A. Nosov, A. E. Pankratiev, V. M. Staroverov

Lomonosov Moscow State University

Abstract: We show that the problem of deciding properness of a family of functions specified by a circuit is coNP-complete, and propose procedures for generation of all proper families of a given order and of uniform distribution on the set of proper families.

Keywords: proper families of functions, Markov chains.