К. Л. Рычков, “О связи нижних оценок сложности схем из функциональных элементов с задачей о минимальном покрытии”, Дискретн. анализ и исслед. опер., сер. 1, 2002, том 9, выпуск 1,страницы 54

О связи нижних оценок сложности схем из функциональных элементов с задачей о минимальном покрытии

К. Л. Рычков

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Приводится обобщение и более “прямое” доказательство теоремы А. А. Разборова [6] о сведении нижних оценок сложности схем из функциональных элементов в базисе $\{\vee,\wedge,\neg\}$ к задаче “минимальное покрытие”.
Библиогр. 6.

УДК: 519.714.4

Статья поступила: 23.09.2001