One approach to construction of effective algorithms for recognizing completeness in multivalued logics (Q1820763)

Let \(E_ k\) be the set \(\{\) 0,1,...,k-1\(\}\) and \(P_ k\) be the set of all functions \(f(\bar x^ n):E^ n_ k\to E_ k\) depending on an arbitrary number n of variables. Let \(S=\{f_ 1(\bar x^ n),...,f_ t(\bar x^ n)\}\) be a system of functions in \(P_ k\). The problem is to determine the completeness of S (or, in other words, whether an arbitrary function from \(P_ k\) can be expressed in terms of the functions from S by means of the composition operation). Functions are defined by tables in which tuples of values of variables are ordered lexicographically, and numbers appearing in the tables are represented by their binary expansions. A function \(f_ i(\bar x^ n)\) is defined by a table whose cardinality is equal to \(k^{n_ i}\cdot (n_ i+1)\cdot \log_ 2k\) and, therefore, the cardinality of the entire input information of the problem of the completeness of system S is equal to \(\bar N=\sum^{t}_{i=1}k^ n\cdot (n_ i+1)\cdot \log_ 2k\). To describe the algorithms, the author uses a model of computation with arbitrary access to the memory. By a step of an algorithm the author means logical operations on bit information, and time complexity of an algorithm is the dependence of the number of steps used by the algorithm to solve the completeness problem on the cardinality of input information. The author constructs algorithms with time complexity \(O(\bar N)\) for \(k=2\), 3, 4 and with time complexity \(O(\bar N\cdot \log \bar N)\) for \(k=5\), 6.