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

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






Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая логика»
24 декабря 2018 г. 14:50–15:25, г. Москва, МИАН, ул. Губкина, д. 8, конференц-зал, 9 этаж
 


Техники уменьшения глубины схем

А. С. Куликов

Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук
Видеозаписи:
MP4 962.7 Mb
MP4 437.1 Mb

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

А. С. Куликов
Фотогалерея


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

Аннотация: Наилучшей нижней оценкой для схем без ограничений на глубину, базис и исходящую степень на протяжении нескольких десятилетий оставалась оценка 3n. Более того, метод элиминации элементов, которым была доказана эта и многие предыдущие оценки, в текущем виде не способен дать оценок сильнее $5n$. В данной работе мы представим способ доказательства нижних оценок, основанный не на элиминации элементов. Мы покажем, что любую схему размера s можно переписать как дизъюнкцию $2^{s/3.9} 16-КНФ$. Несмотря на то, что этот структурный результат не даёт немедленно новые нижние оценки, он даёт новый потенциальный способ.
Наш результат дополняет классический результат Вэлиэнта 70-х годов, который говорит, что любую схему линейного размера и логарифмической глубины можно переписать как дизъюнкцию$ 2^{an} n^b-КНФ$ (где a, b — константы). Известно, что такой графовый подход не даёт нетривиальных оценок для схем суперлогарифмической глубины. Мы обходим это препятствие, рассматривая не только граф схемы, но и то, какие вычисления происходят внутри.

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