Laboratory of Mathematical Logic at PDMI

Пятница, 16 марта, комната 106. Начало в 15:30.

Докладчик: С. Николенко.

Тема: Канонические NP-пары и системы доказательств.

Abstract

Доклад по статье Christian Glasser, Alan L. Selman, Liyu Zhang ``The Informational Content of Canonical Disjoint NP-Pairs'', http://eccc.hpi-web.de/eccc-reports/2007/TR07-018/index.html

Очевидно, что из сведения между системами доказательств следует сведение между их каноническими NP-парами. В докладе будет рассмотрен обратный вопрос: что следует из сведения между каноническими NP-парами криптосистем? Приводятся новые классы контрпримеров - системы доказательств с разной силой, но эквивалентными каноническими NP-парами. Изучается вопрос о том, что же всё-таки следует из эквивалентности канонических NP-пар.