Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 12/2013

НИЖНИЕ ОЦЕНКИ НА РАЗМЕР РЕЗОЛЮЦИОННЫХ ДОКАЗАТЕЛЬСТВ НЕКОТОРЫХ СЛАБЫХ ФОРМУЛ

This preprint was accepted November 14, 2013

АННОТАЦИЯ:
Мы доказываем, что для каждого d и для достаточно больших n для каждой
последовательность натуральных чисел d_1, d_2, ..., d_n, не превосходящих
 d можно  построить граф на n вершинах, степень которого ограничена константной (но степень
i-й вершины не меньше d_$), что из графа нельзя удалить несколько ребер так,
чтобы в получившемся графе степень i-й вершины равнялась d_i и доказательство
этого утверждения в резолюциях имеет размер 2^{\Omega(n)}.  Из этого результата
следуют известные результаты об экспоненциальных нижних оценках для принципа
 Дирихле и цейтинских формул.

Мы доказываем, что древовидная резолюционная сложность формулы,
 которая кодирует невозможность разбиения квадрата n на n на доминошки
 при нечетных n,  равняется 2^{\Theta(n)}.

Мы доказываем, что древовидная резолюционная сложность CSP задачи, которая
кодирует утверждение о том, что невозможно в каждую клетку квадрата 
$n \times n$ расставить по одной стрелке (стрелки могут быть направлены
 горизонтально, вертикально или по диагонали), так чтобы стрелки в двух 
соседних клетках отличались поворотом не   более, чем на 45 градусов,
 а стрелки на границе квадрата не были бы  направлены вне квадрата, 
равняется 2^{\Theta(n)}.

 

D. M. Itsykson, M. G. Slabodkin, V. V. Oparin, D. O. Sokolov

ABSTRACT:
We prove that for every natural number d and for every n large 
enough for every numbers d_1, d_2, ..., d_n that are at most d
 it is possible to construct a graph with n vertices that has 
the following properties. The degree of every vertex is bounded 
by a constant (but the degree of the i-th vertex is at least d_i) 
and it is impossible to remove edges from this graph such that 
degree of $i$-th vertex would be equal to d_i.  And a proof of 
this statement in the resolution proof system has size 2^{\Omega(n)}.
 This result implies well-known exponential lower bounds on 
the resolution complexity of pigeonhole principle and Tseitin formulas.

We prove that a formula that encodes impossibility of partition
 square n by n by dominoes for odd n has tree-like resolution 
complexity 2^{\Theta(n)}.
 
We consider a CSP problem that encodes the fact that it is
 impossible to match cells of n by n square to arrows (two horizontal,
 two vertical and four diagonal) such that arrows in the two cells
 with a common edge differ in at most 45 degrees and all arrows on
 the boundary of the square do not look outside. And we prove that
 tree-like resolution complexity of this CSP is 2^{\Theta(n)}.


 Key words:  resolution, proof system, expander, decision tree, PPA, PPAD



[Full text:
 Preprint in Russian (.pdf.gz)







Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg