Laboratory of Mathematical Logic at PDMI

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

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

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

Abstract

Доклад по статье O.Beyersdorff (ECCC TR 05-083).

Класс непересекающихся пар языков из NP тесно связан с изучением криптосистем. Abstract статьи:

For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard or complete for DNPP(P). Moreover we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist.