Вестник Московского Университета. Математика, Механика - Содержание


УДК 519.6

О сложностной иерархии булевых базисов / Черухин Д.Ю. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2000. N 3 C. 48-50.

Исследуется зависимость сложности булевых функций в классе формул от функционального базиса. В связи с этим на множестве базисов вводится отношение частичного порядка (как это было сделано в работах Б.А. Субботовской, В.А. Стеценко и автора). Основным результатом работы является критерий, позволяющий устанавливать выполнимость этого отношения для произвольных базисов.

Библиогр. 4.

img SRC="http://vestnik.math.msu.su/Images/k-ogl-nom.gif" width="146" height="14" alt="К оглавлению номера" border="0" align="middle">  Go!