On the computational complexity of finite operations

DOI10.1142/S0129054116500027MaRDI QIDQ2806555zbMATH OpenFDO

Authors Slavcho Shtrakov, Ivo Damyanov

Publication date 18 May 2016

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.00265

zbMATH Keywords

implementationordered decision diagramseparable setsubfunction

Mathematics Subject Classification ID

Many-valued logic (03B50) Boolean functions (06E30) Operations and polynomials in algebraic structures, primal algebras (08A40) Analysis of algorithms and problem complexity (68Q25)

Abstract: The essential variables in a finite function $f$ are defined as variables which occur in $f$ and weigh with the values of that function. The number of essential variables is an important measure of complexity for discrete functions. When replacing some variables in a function with constants the resulting functions are called subfunctions, and when replacing all essential variables in a function with constants we obtain an implementation of this function. Such an implementation corresponds with a path in an ordered decision diagram (ODD) of the function which connects the root with a leaf of the diagram. The sets of essential variables in subfunctions of $f$ are called separable in $f$. In this paper we study several properties of separable sets of variables in functions which directly impact on the number of implementations and subfunctions in these functions. We define equivalence relations which classify the functions of $k$-valued logic into classes with same number of implementations, subfunctions or separable sets. These relations induce three transformation groups which are compared with the lattice of all subgroups of restricted affine group (RAG). This allows us to solve several important computational and combinatorial problems.

Review text

The question on the complexity of \(k\)-valued functions has been studied by various authors as a contribution to the theory of computation. The present paper deals with two ways of a construction of new functions: subfunctions and implementations; decomposition trees correspond to the first one and ordered decision diagrams correspond to the latter.NEWLINENEWLINELet \(G\) be a transformation group acting on the algebra \(P^n_k\). Then, the authors introduce a \(G\)-equivalence of functions. For various transformation groups \(G\), properties of the equivalence are investigated: the number of the equivalence classes, the cardinality of the classes, a method of a classification of a function, first for a general case.NEWLINENEWLINE The last section of the paper is devoted to Boolean functions \(f\in P_2^n\) (even for \(n\leq 6\), very large cardinalities have been obtained and they had to be calculated on a computer).NEWLINENEWLINEThe text is enriched by a couple of illustrating examples.

Recommendations

• On the computational complexity of some classical equivalence relations on boolean functions
• On recognition complexity for systems of functions in the class P^*_3
• scientific article; zbMATH DE number 437436
• On the classification of Boolean functions.
• On recognition of some properties of systems of finite-valued functions

Cited in

(5)

• Operational complexity and pumping lemmas
• scientific article; zbMATH DE number 6672540 (Why is no real title available?)
• scientific article; zbMATH DE number 5901113 (Why is no real title available?)
• Computing in Finite Time
• scientific article; zbMATH DE number 4066861 (Why is no real title available?)

This page was built for publication: On the computational complexity of finite operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806555)