Для системы доказательств CP известен только один метод доказательства нижних оценок --- метод интерполяции, т.е. построение по короткому доказательству в CP короткой монотонной схемы для подсчета некоторой функции. Таким образом, чтобы доказать нижнюю оценку для CP достаточно доказать нижнюю оценку на монотонные схемы. Одной из существенных проблем данного метода является то, что он может быть применен лишь к узкому классу формул. В докладе мы обобщим метод интерполяции на формулу произвольного вида и докажем нижнюю оценку для случайной log(n)-КНФ формулы.

Доклад по статье:
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
Random CNFs are Hard for Cutting Planes