Теоретический семинар (весна 2015)

Мы рассмотрим технику, позволяющую доказать, что у задачи нет полиномиального ядра.
Основной целью доклада будет рассказать доказательство факта, что наличие алгоритма, который переводит много инстансов языка в один, эквивалентный дизъюнкции этих инстансов, приводит к сомнительному, с точки зрения полиномиальной иерархии, включению $\mathrm{NP}\subset\mathrm{co{-}NP/poly}$.
Мы рассмотрим задачу определения BANDWIDTH графа, $NP$-сложную задачу, в которой вершинам графа нужно сопоставить различные метки, минимизируя при этом максимум абсолютной разности меток на концах ребра.

Будет рассмотрен алгоритм, основанный на смеси перебора и динамического программирования, лучший из известных на данный момент, за $O^*(5^n)$.

Мы познакомимся с теорией типов с интервалом и условиями, продемонстрируем возможность определения в ней типа, соответствующего произвольному конечному CW-комплексу. Изучим преимущества данной теории типов по сравнению со стандартной гомотопической теорией типов, а также докажем теорему о произведении типов, соответствующих конечным CW-комплексам, аналогичную классической теореме о произведении CW-комплексов.

We prove exponential lower bounds on the running time of DPLL with splitting by linear combinations on formulas that encode the pigeonhole principle. We consider an extension of the resolution proof system that operates with disjunctions of linear equalities over $F_2$ and we call this system Res-Lin. Res-Lin can be p-simulated in R(lin) but currently we do not know any superpolynomial lower bounds in R(lin). Tree-like proofs in Res-Lin are equivalent to the behavior of our algorithms on unsatis able instances.

We prove exponential lower bounds on the running time of DPLL with splitting by linear combinations on formulas that encode the pigeonhole principle. We consider an extension of the resolution proof system that operates with disjunctions of linear equalities over $F_2$ and we call this system Res-Lin. Res-Lin can be p-simulated in R(lin) but currently we do not know any superpolynomial lower bounds in R(lin). Tree-like proofs in Res-Lin are equivalent to the behavior of our algorithms on unsatis able instances.

Сформулируем задачу об аренде серверов в облаке. Дадим нижнюю оценку на конкруентоспособность (competitive ratio) для любого онлайн алгоритма. Представим алгоритм Next-Fit и его модифированную версию, верхние оценки на их конкурентоспособность.