Laboratory of Mathematical Logic at PDMI

Вторник, 9 сентября, комната 106. Начало в 15:00.

Докладчик: Д. Ицыксон.

Тема: Системы доказательств с подсказками.

Abstract

Доклад по статье O. Beyesdorff, J. Kobler,, S. Muller, Nondeterministic Instance Complexity and Proof Systems with Advice.

В докладе будет рассказано о системах доказательств с подсказками. Будет построена оптимальная система доказательств с одним битом подсказки (без подсказки такая система неизвестна). Будет затронут вопрос о том, для каких языков существует системы доказательств с подсказкой, в которых все доказательства имеют короткую длину.

Для понимания доклада необходимо быть знакомым со следующими понятиями: пропозициональная система доказательств, класс NP, вычисления с неравномерной подсказкой (те, что эквивалентны булевым схемам).