RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Колмогоровский семинар по сложности вычислений и сложности определений
1 апреля 2013 г. 16:45–18:25, г. Москва, Главное здание МГУ, ауд. 16-04
 


Пороговые элементы на множестве $\{1,2\}$ и пороговые схемы

В. В. Подольский

Количество просмотров:
Эта страница:94

Аннотация: Полиномиальным пороговым элементом для булевой функции $f\colon\{a,b\}^n\to\{a,b\}$ называется целочисленный многочлен $p$ от $n$ переменных, такой что для всякого $x$ из $\{a,b\}^n$ верно $p(x)>0$ тогда и только тогда, когда $f(x)=b$. Обычно, когда говорят о вычислении булевых функций пороговыми элементами, булевы функции рассматриваются как функции на переменных $\{0,1\}$ или $\{-1,1\}$. В рамках доклада мы будем рассматривать реализацию пороговыми элементами булевых функций с произвольными значениями переменных $\{a,b\}$. Типичным случаем являются значения переменных $\{1,2\}$. Основной мерой сложности пороговых элементов будет число мономов в них, второй мерой сложности будет степень пороговых элементов. Оказывается, что эта модель вычислений сильнее чем аналогичные модели над переменными $\{0,1\}$ и $\{-1,1\}$. Кроме того, оказывается, что эта модель тесно связана с пороговыми схемами глубины $2$. Эта связь является основной мотивацией для изучения пороговых элементов над переменными $\{1,2\}$.
В докладе будет рассказано о структурных результатах о пороговых элементах над переменными $\{1,2\}$ и о связи этих пороговых элементов с пороговыми схемами.
Доклад основан на совместной работе с Кристоффером Хансеном. Ссылка на работу: http://eccc.hpi-web.de/report/2013/021/

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018