The article investigates the complexity of implicit representations for functions of k-valued logic. A function f is implicitely representable over A, if there exists a system of equations written with the use of variable symbols and function symbols from A whose unique solution is the function f. For implicitely complete classes (i.e. the ones which allow the implicit representation of an arbitrary function) we consider the rank function: the smallest number of equations that is sufficient for implicitely representing an arbitrary function on n variables over this given class. The article presents examples of impicitely complete classes with rank functions of an exponential growth order. All minimal implicitely complete classes of functions in three-valued logic have their rank functions investigated and we find their order of growth, and, for some of the classes, an exact expression. This, in particular, allows to show that the rank function order of growth for all of these classes is either linear or exponential. Besides that we establish sufficient conditions for a class to be imlicitely complete in k-valued logic and for all classes that meet these conditions we find an explicit expression of the rank function, which has linear order of growth.

k-valued logic, implicit representation, complexity, order of growth, implicit completeness

Mathematical problems and theory of numerical methods