Том 9, серия 1, номер 1, 2002 г., Стр. 54-58
УДК 519.714.4
К. Л. Рычков
О связи нижних оценок сложности схем из функциональных элементов с задачей о минимальном покрытии
Аннотация:
Приводится обобщение и более “прямое” доказательство теоремы А. А. Разборова [6] о сведении нижних оценок сложности схем из функциональных элементов в базисе$\{\vee,\wedge,\neg\}$ к задаче “минимальное покрытие”.
Библиогр. 6.
Рычков К. Л. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 23 сентября 2001 г.
