О нижних оценках сложности систем векторов $k$-значной логики

Исследуется сложность порождения систем векторов схемами в базисах $B_{k,1}$, $B_{k,2}$, $B_{k,3}$, где $B_{k,1}$ — множество всех не более чем двуместных операций $k$-значной логики, $B_{k,2}$ — множество всех не более чем одноместных операций $k$-значной логики, содержащее также двуместные операции $\max$ и $\min$, $B_{k,3}$ — множество всех не более чем одноместных монотонных операций $k$-значной логики, содержащее также двуместные операции $\max$ и $\min$. Основными результатами работы являются нижние оценки сложности порождения систем векторов и соотношения, связывающие нижние оценки сложности порождения систем векторов и нижние оценки сложности функций $k$-значной логики. Из этих соотношений следует, что установление нижних оценок сложности порождения узких систем векторов, асимптотически больших, чем полученные в этой работе, влечет установление экспоненциальных нижних оценок сложности функций $k$-значной логики при их реализации схемами в полных базисах. Под узкими системами понимаются системы, у которых число векторов по порядку не превосходит логарифма числа компонент этих векторов. Ранее автором были получены аналогичные результаты для систем булевых векторов.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 96-01-01068.