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

Поиск
RSS
Новые поступления





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






Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика»
18 декабря 2009 г. 16:00, г. Москва
 


О некоторых классах пороговых булевых схем ограниченной глубины

В. В. Подольский
Видеозаписи:
Real Video 119.7 Mb
Windows Media 122.0 Mb
Flash Video 129.2 Mb
MP4 129.2 Mb

Количество просмотров:
Эта страница:452
Видеофайлы:164

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


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: Пороговой функцией называется булева функция $f$ от $n$ переменных, которая задается знаком целочисленного линейного многочлена $p$ от этих переменных. Пороговой схемой называем схему, составленную из пороговых функций.
Пороговые функции и схемы играют важную роль в теории сложности булевых схем. Одной из важнейших открытых проблем в этой области является доказательство того, что какая-либо явно заданная булева функция не может быть реализована пороговыми схемами глубины 2 полиномиального (от числа переменных) размера.
Докладчиком (совместно с Кристоффером Хансеном) предложена серия новых типов булевых схем ограниченной глубины. Каждому типу схем сопоставляется класс всех булевых функций, реализуемых схемами полиномиального размера данного типа. Оказывается, что эти новые классы функций хорошо вписываются в известную иерархию классов, задаваемых пороговыми схемами ограниченной глубины. Мы исследуем соотношения между этими классами.
Мы также рассматриваем вопрос о существовании явно заданной булевой функции, не принадлежащей одному из наших классов. Мы доказываем, что этот вопрос не сложнее сформулированного выше вопроса о сложности реализации булевых функций пороговыми схемами глубины2. Мы надеемся, что решение нашего вопроса даст новую технику для решения этой известной открытой проблемы.

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