Laboratory of Mathematical Logic at PDMI

Пятница, 25 февраля, комната 106. Начало в 17:30.

Докладчик: Р. Мясников.

Тема: Представимые дизъюнктные NP-пары.

Abstract

Необходимость исследования класса DNPP (пар непересекающихся языков из NP) естественным образом возникает при рассмотрении ряда криптографических задач, в частности, при попытках доказательства надежности конкретных криптосистем (например, RSA). В 1994 году А.А.Разборов предложил в качестве инструмента исследования DNPP использовать связь этого класса с пропозициональными системами доказательств. С использованием этой техники будет описана структура DNPP и будет сделана попытка приблизиться к ответу на вопрос о существовании DNPP-полных пар относительно ряда сведений в DNPP.