On recognition complexity for systems of functions in the class \(P^*_3\) (Q1280364)

Let \(P^*_k\) be the set of all partial functions of \(k\)-valued logic and \(P_k\) be the set of everywhere defined functions from \(P^*_k\). The authors discuss the complexity of an algorithm which recognizes the completeness of systems of functions in the class \(P^*_3\) with respect to superposition. It is assumed that the functions are defined by the vectors of their values for a fixed order of the sets of variables. In addition, non-branching bit calculations are taken as algorithms. The authors prove that there exists an algorithm with bit complexity \(O(N^{\log_36}\log_2^2N)\), where \(N\) is the length of the input information.