Видеотека: В. В. Подольский, О некоторых классах пороговых булевых схем ограниченной глубины

ВИДЕОТЕКА


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

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