авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |

«Российская академия наук САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМЕНИ В.А. СТЕКЛОВА РАН УДК 510.6 ГРНТИ 27.03.19 Инв. ...»

-- [ Страница 3 ] --

3 Алгебраические основы теории эллиптических кривых Эллиптические кривые. Определение эллиптической кривой. Неприводимые компоненты. Сингулярные и несингулярные точки. Грубая оценка числа точек кривой над конечным полем. Теорема Хассе. Результанты.

Основное свойство результантов. Числа пересечений. Существование и единственность числа пересечений. Результанты. Основное свойство результантов. Числа пересечений.

Существование и единственность числа пересечений. Теорема Безу. Определение сложения на эллиптической кривой. Групповой закон на эллиптических кривых.

4 Криптография на эллиптических кривых – 113 – Уравнение Вейерштрасса. Канонический вид уравнения эллиптической кривой для характеристик 2, 3 и всех остальных. Формулы вычисления группового закона в координатах.

Координаты Якоби и их преимущества. Задача дискретного логарифма на эллиптической кривой.

5 Задача разложения на множители Разложение чисел на множители. Метод Ферма, метод Крайчика. Алгоритм квадратичного решета. Просеивание значений многочлена.

6 Задача дискретного логарифма Задача дискретного логарифма. Метод Полига Хеллмана, ро-метод Полларда. Идея алгоритма исчисления индексов (index calculus). Алгоритма исчисления индексов и оценка его сложности.

7 Схемы разделения секрета.

Разделение секрета (secret sharing). Схема Блэкли, схема Шамира. Verifiable secret sharing (VSS).

Proactive secret sharing (PSS).

8 Интерактивные системы доказательств Интерактивные системы доказательств (IPS).

Полнота и корректность. Примеры IPS для задач ISO и NISO. Свойство неразглашения для IPS (zero knowledge). VIEW и его симулятор.

Определение ZK. ZK-протокол для ISO. (Не совсем ZK)-протокол для NISO. Варианты определения ZK в зависимости от возможностей симулятора. ZK с подсказкой (advice). Настоящий ZK-протокол для NISO, доказательство его корректности, полноты и неразглашения.

9 Oblivious transfer и конфиденциальные вычисления Протоколы oblivious transfer: протокол Рабина и 1-2 OT. Детерминированное конфиденциальное вычисление (secure multi-party computation).

Схема обязательcтва (bit commitment). Бросание монетки в колодец. Вероятностное конфиденциальное вычисление (покер по телефону).

10 Некоммутативная криптография Идея и обоснование необходимости некоммутативной криптографии. Основные некоммутативные конструкции: протокол Ко-Ли, протокол Аншель-Аншеля-Голдфельда. Группы кос: определения и свойства. Криптографические протоколы, основанные на группах кос. Атаки на такие протоколы.

ВСЕГО – 114 – 4. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория Математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

5. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Рекомендованная литература 1. В. В. Ященко и др. Введение в криптографию. М., Изд-во МЦНМО, 2000.

2. A. J. Menezes, P. van Oorschot, S. Vanstone (eds). Handbook of applied cryptography. CRC Press, 1996.

3. J. Katz, Y. Lindell. Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall / CRC Press, 2007.

Дополнительная литература 1. J. H. Silverman. The Arithmetic of Elliptic Curves. Springer, 2009.

2. O. Goldreich. Foundations of Cryptography. Volume I: Basic Tools. Cambridge University Press, 2007.

3. O. Goldreich. Foundations of Cryptography. Volume II: Basic Applications. Cambridge University Press, 2009.

4. D. Hankerson, A. J. Meneses, S. Vanstone. Guide to Elliptic Curve Cryptography. Springer, 2010.

– 115 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ОПД.АФ.03. «Эффективные алгоритмы».

основной образовательной программы послевузовского профессионального образования по научной специальности 05.13. Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 01.00.00 Физико математические науки Программа составлена м.н.с., к.ф.-м.н. А. С. Куликов РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2010 г 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является основной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 05.13.17 – Теоретические основы информатики.

Целью преподавания данной дисциплины является подготовка высококвалифицированных специалистов в области теоретической информатики. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ Задачей дисциплины является изучение эффективных алгоритмов, не входящих в базовый курс. В частности, вероятностных алгоритмов, алгоритмов для NP-трудных задач, FPT-алгоритмов, алгоритмов, обрабатывающих вход по мере поступления.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ – 116 – Виды занятий и форма контроля часы Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов 2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Приближённые алгоритмы Приближенные алгоритмы для задач о вершинном покрытии и о покрытии множествами.

Приближенный алгоритм для задачи о кратчайшей надпоследовательности.

Приближенный алгоритм для задачи о коммивояжере в метрическом пространстве, полностью полиномиальная приближенная схема для задачи о рюкзаке. Постановка задачи полуопределённого программирования, приближённый алгоритм для задачи о максимальном разрезе, раскраска 3– раскрашиваемого графа. Постановка задачи полуопределённого программирования, приближённый алгоритм для задачи о максимальном разрезе, раскраска 3– раскрашиваемого графа.

2 Вероятностные алгоритмы Проверка перемножения матриц, сравнение строк, корни многочлена, эквивалентность ветвящихся программ. Минимальный разрез, проверка простоты числа. Поиск расстояний в графе, поиск виновников в умножении булевых матриц, поиск кратчайших путей в графе. Линейный вероятностный алгоритм нахождения минимального покрывающего дерева. Алгоритм и оценки времени его работы в худшем и среднем случае. Метод условных вероятностей, метод малых пространств событий.

3 Алгоритмы для задачи выполнимости Расщепляющие алгоритмы (DPLL, PPSZ), случайные блуждания.

4 Подходы к решению NP–трудных задач Расщепление, случайный порядок перебора, локальный поиск, динамическое программирование, сведение к простой задаче, случайное сведение к простой задаче, умный перебор.

5 Задача линейного программирования Потоки в сетях, максимальное паросочетания в двудольном графе, двойственность, симплекс– – 117 – метод. Алгоритм Кармаркара.

6 Динамическое программирование Наибольшая возрастающая подпоследовательность, стоимость редактирования, рюкзак, перемножение нескольких матриц, кратчайшие пути, независимые множества в деревьях.

7 Жадные алгоритмы Задача о выборе заявок, коды Хаффмена, покрытие множествами, вершинное покрытие, локальный поиск для задачи выполнимости.

8 Нахождение максимального потока Метод Форда–Фалкерсона, алгоритм проталкивания предпотока, алгоритм «поднять-и в–начало». Вероятностное округление для задачи о потоке в сетях с несколькими веществами.

9 Алгоритмы, обрабатывающие вход по мере поступления Задача кэширования, задача о покрытии множествами.

ВСЕГО 3. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

4. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

5. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Рекомендованная литература Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, 2006.

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, • Cambridge, second edition, 2001.

А. Шень. Программирование: теоремы и задачи. М., МЦНМО, 2-е издание, 2004.

• R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

• – 118 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ОПД.АФ.03. «Математическая логика и теория алгоритмов».

основной образовательной программы послевузовского профессионального образования по научной специальности 05.13.17.

Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 01.00.00 Физико математические науки Программа составлена м.н.с., к.ф.-м.н. Д.М. Ицыксон РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2009 г 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является основной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 05.13.17 – теоретические основы информатики.

Целью преподавания данной дисциплины является подготовка высококвалифицированных специалистов в области математической логики и теории алгоритмов. В курсе особое внимание уделяется развитию у учащихся навыков самостоятельного анализа решений различных задач математической логики.

2. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ Задачей дисциплины является изучение основных логических исчислений, основ теории алгоритмов и сложности вычислений, основ теории моделей. После освоения курса аспиранты – 119 – должны оперативно владеть основными понятиями и методами математической логики и теории алгоритмов, строить аксиоматизации разрешимых теорий, проводить элиминацию кванторов, выяснять алгоритмическую разрешимость вычислительных задач, уметь доказывать NP-полноту массовых проблем.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ Виды занятий и форма контроля часы Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Аксиоматическая теория множеств.

Аксиомы теории множеств. Фундированные множества, вполне упорядоченные множества.

Трансфинитная индукция. Теорема Цермело.

Лемма Цорна. Арифметика ординалов.

2 Исчисление высказываний Формулы исчисления высказываний. Булевы функции и их представление в КНФ и ДНФ.

Алгоритм приведения в КНФ/ДНФ. Булевы схемы. Эффективная булева схема для сложения чисел. Гильбертовское исчисление высказываний.

Корректность. Лемма о дедукции. Основные правила натурального вывода. Теорема о полноте гильбертовского исчисления. Исчисление секвенций. Резолюционная система доказательств.

3 Исчисление предикатов Формулы исчисления предикатов. Аксиомы исчисления предикатов. Лемма о дедукции в исчислении предикатов. Лемма о свежих константах Теорема о полноте. Теорема Левенгельма-Сколема о существовании счетной модели. Теорема Мальцева о компактности.

Предваренная нормальная форма. Теорема Эрбрана. Скулемизация.

4 Языки первого порядка Невыразимые предикаты: метод автоморфизмов.

Элиминация кванторов: арифметика Пресбургера, элементарная теория вещественных чисел (Теорема Тарского), алгебраически замкнутые поля, теория плотного линейного порядка.

5 Вычислимые функции Понятие алгоритма и его уточнения.

Вычислимость по Тьюрингу, частично рекурсивные функции, рекурсивно перечислимые и рекурсивные множества. Тезис Чёрча.

– 120 – Универсальные вычислимые функции.

Существование перечислимого неразрешимого множества. Теорема Успенского-Райса. Теорема о неподвижной точки. Неразрешимость исчисления предикатов. Построение полугруппы с неразрешимой проблемой распознавания равенства. Главные нумерации. Примитивно рекурсивные функции.

6 Арифметика Выразимость в арифметике. Бета-функции Геделя, арифметичность вычислимых функций.

Арифметическая иерархия. Универсальные множества в арифметической иерархии. Операция скачка. Строгость арифметической иерархии. m cведения. Теоремы Тарского о невыразимости и Геделя о неполноте арифметики. Вторая теорема Геделя о неполноте. Арифметика Пеано.

7 Введение в теорию сложности вычислений Универсальная машина Тьюринга.

Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи ВЫПОЛНИМОСТЬ. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм Левина. Теорема Ладнера. Полиномиальная иерархия.

8 Элементы теории моделей Основные определения теории моделей.

Выводимость и теорема о полноте. Теорема о компактности. Следствия: невыразимость множества точек кручения, нестандартная модель натуральных чисел. Аксиомы равенства и нормальные модели. Повышение мощности модели. L-структуры, подструктуры и расширения. Теории и модели. Логические следствия. Выразимые множества. Примеры теорий и выразимых множеств. Элементарные теории классов алгебраических систем.

Категоричные в данной мощности теории.

Теорема о полноте теории, не имеющей конечных моделей и категоричной в бесконечной мощности.

ВСЕГО 4. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория Математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

5. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ – 121 – Рекомендованная литература 4. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1.

Начала теории множеств. М.: МЦНМО, 2-е изд, 2008.

5. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2.

Языки и исчисления. М.: МЦНМО, 2-е изд, 2002.

6. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3.

Вычислимые функции. М.: МЦНМО, 2-е изд. 2002.

7. Ершов Ю.Л., Палютин Е.А. Математическая логика. 2-е изд. М.: Наука, 1987.

8. Мальцев А.И. Алгоритмы и рекурсивные функции. 2-е изд. М.: Наука, 1986.

9. Мендельсон Э. Введение в математическую логику. 3-е изд. М.: Наука, 1984.

10. Новиков П.С. Элементы математической логики. 2-е изд. М.: Наука, 1973.

Дополнительная литература 1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. Мир, 1982.

2. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М.: Наука, 1980.

3. D. Marker. Model Theory: An Introduction. Springer-Verlag New York, 2002.

4. H.-D. Ebbinghaus, J. Flum, W. Thomas. Mathematical Logic. Springer-Verlag New York, 1984.

– 122 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ОПД.АФ.00. «Вероятностные и алгебраические методы в информатике».

основной образовательной программы послевузовского профессионального образования по научной специальности 05.13.17.

Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 01.00.00 Физико математические науки Программа составлена м.н.с., к.ф.-м.н. А. В. Куликов РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2009 г 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является факультативной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 05.13.17 – теоретические основы информатики. Целью преподавания данной дисциплины является подготовка высококвалифицированных специалистов в области теории сложности вычислений. Курс посвящен изучению вероятностных и алгебраических методов в информатике.

2. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ Задачей дисциплины является изучение вероятностных и алгебраических методов в информатике.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ Виды занятий и форма контроля часы Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов – 123 – 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа.

2 Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга.

Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике. Кодирование конечных последовательностей.

3 Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения.

Универсальные множества. Теоремы Тарского и Геделя.

4 Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо.

5 Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–SAT.

6 Локальная лемма Ловаса. Оценки Чернова. 7 Метод второго момента. Порог для 4–клики. Сепараторы.

8 Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона.

Код Рида–Соломона. Каскадные коды.

9 Теорема Форни. Оценки Плоткина. Код Адамара. Код Рида–Маллера. Код БЧХ.

ВСЕГО 4. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

5. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Рекомендованная литература 4. А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления. М.: МЦНМО, 1999, 192 с.

5. S.Arora, B.Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

6. O.Goldreich. Foundations of cryptography. Vol. 1-2, Cambridge Unversity Press, 2001.

– 124 – Дополнительная литература 4. C.Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

5. A. Bogdanov, L. Trevisan. Average-case complexity. Foundation and Trends in Theoretical Computer Science, 2(1):1_106, 6. S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, vol.

43, Number 4, Oct. 2006, pp.439– – 125 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ОПД.АФ.03. «Теоретическая криптография».

основной образовательной программы послевузовского профессионального образования по научной специальности 05.13. Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 05.00.00 Технические науки Программа составлена м.н.с., к.ф.-м.н. Д.М. Ицыксон РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2009 г 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является основной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 05.13.17 – теоретические основы информатики. Сложностная криптография служит теоретической основой современной практической криптографии. Целью изучения дисциплины является знакомство студентов с фундаментальными основными криптографии, методами доказательства надежности криптографических протоколов 2. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ Задачей дисциплины является изучение основных понятий и конструкций теоретической криптографии, связи криптографии и теории сложности, в частности, теории сложности в среднем.

После освоения курса аспиранты должны владеть основными понятиями и методами современной теоретической криптографии, понимать современное состояние "переднего края" теоретической криптографии. Курс готовит аспирантов к самостоятельной научной работе.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ Виды занятий и форма контроля часы – 126 – Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Односторонние функции Односторонние в наихудшем случае функции.

Односторонние функции,соглашения о длинах входа. Сильные и слабые односторонние функции. Семейство односторонних функций.

Универсальная односторонняя функция. Трудный бит и его существование.

2 Псевдослучайные конструкции в криптографии Вычислительная неразличимость и ее свойства.

Односторонняя функция из генератора псевдослучайных чисел. Конструкция генератора. Неразличимость повторных распределений. Семейство псевдослучайных функций..

3 Основные криптографические протоколы Протокол с секретным ключом. Семейства односторонних перестановок с секретом, примеры. Протокол с открытым ключом 4 Доказательство с нулевым разглашением Доказательства с совершенно нулевым разглашением, доказательства с вычислительно нулевым разглашением. Протокол для изоморфизма графов. Нулевое разглашение с использованием дополнительной информации.

Нулевое разглашения для класса.

5 Схемы электронной подписи Одноразовый протокол электронной подписи одного бита. Одноразовый протокол электронной подписи фиксированного полиномиального числа битов. Одноразовый протокол электронной подписи произвольных сообщений полиномиальной длины на основе СТОК.

Построение СТОК через СТОЗ. Конструкция СТОЗ. Одноразовый протокол электронной подписи произвольных сообщений полиномиальной длины на основе универсального семейства односторонних функций.

Многоразовый протокол электронной подписи.

6 Сложность в среднем и криптография Распределенные задачи. Полиномиальность в среднем по Левину и Импальяццо. Пример – 127 – распределения, для которого сложность в среднем и наихудшем случае эквивалентны.

Доминирование распределений. Универсальное полиномиально моделируемые распределение.

Сведения. Полная задача в.

Обратимые полиномиально моделируемые распределения ( ). Вычислимые распределения, включение. Полнота задачи об ограниченной остановке в. Классы,, задачи поиска.

Универсальные семейства хеш-функций. Лемма Вэлиэнта-Вазирани для универсального семейства хэш-функций. Сведение задач поиска к задачам распознавания. Вероятностные сведения для задач поиска. Замкнутость класса относительно этих сведений. Вероятностное сведение к. Из существования полной задачи с равномерным распределением относительно етерминированных сведений следует, что.

Односторонние функции и трудные задачи в.

ВСЕГО 4. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория Математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

5. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Рекомендованная литература 11. O.Goldreich. Foundations of cryptography. Vol. 1-2, Cambridge Unversity Press, 2001.

12. S.Arora, B.Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

13. A. Bogdanov, L. Trevisan. Average-case complexity. Foundation and Trends in Theoretical Computer Science, 2(1):1_106, 2006.

Дополнительная литература 1. S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity.

Journal of Computer and System Sciences, 44(2):193-219, 1992.

2. R. Impagliazzo. A personal view of average-case complexity. In Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p. 134-145, Washington, DC, USA, 3. N. Vereshchagin. An encoding invariant version of polynomial time computable distributions. In Proceedings of the 5th International Computer Science Symposium in Russia (CSR2010), volume 6072 of Lecture Notes in Computer Science, pages 371_383, 2010.

– 128 – 4. R. Impagliazzo and L. Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 812_821, 1990.

5. J. Hastad, R. Impagliazzo, L.A.. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999.

– 129 – Приложение В настоящем Приложении приводятся оттиски публикаций по результатам государственного контракта, вышедшие или поданные к публикации во время исполнения второго этапа работ.

– 130 – Contents Chapter 1. Introduction 1.1. Cryptography in computer science 1.2. Computational models 1.3. Basic denitions of modern cryptography 1.4. What can we prove about security? Chapter 2. Complete one-way functions 2.1. Introduction 2.2. Distributional accessibility problem for semi-Thue systems 2.3. Post Correspondence Problem 2.4. The complete one-way Tiling function 2.5. A complete one-way function based on semi-Thue systems 2.6. A complete one-way function based on Post Correspondence 2.7. Complete one-way functions and DistNP-hard problems 2.8. Generalizing complete one-way functions 2.9. Conclusion Chapter 3. Feebly secure cryptographic primitives 3.1. Introduction 3.2. Denitions 3.3. Matrices of hard functions 3.4. Gate elimination 3.5. Nonlinear feebly secure one-way functions 3.6. Three constructions 3.7. A feebly secure trapdoor function 3.8. Hardness amplication 3.9. Conclusion – 131 –3 | | Chapter 4. Provable break and algebraic cryptography 4.1. Algebraic cryptography 4.2. Provable break 4.3. Denitions 4.4. Invariant-based cryptosystems and their provable break 4.5. The tree of groups 4.6. Leaves of the tree 4.7. Attacks on invariant-based cryptosystems 4.8. The Anshel-Anshel-Goldfeld key agreement protocol secure against provable break 4.9. Conclusion Acknowledgements References – 132 –4 | | An Elementary Proof of a 3n o(n) Lower Bound on the Circuit Complexity of Ane Dispersers Evgeny Demenkov1 and Alexander S. Kulikov St. Petersburg State University St. Petersburg Department of Steklov Institute of Mathematics Abstract. A Boolean function f : Fn F2 is called an ane disperser of dimension d, if f is not constant on any ane subspace of Fn of di mension at least d. Recently Ben-Sasson and Kopparty gave an explicit construction of an ane disperser for sublinear d. The main motiva tion for studying such functions comes from extracting randomness from structured sources of imperfect randomness. In this paper, we show an other application: we give a very simple proof of a 3n o(n) lower bound on the circuit complexity (over the full binary basis) of ane dispersers for sublinear dimension. The same lower bound 3n o(n) (but for a com pletely dierent function) was given by Blum in 1984 and is still the best known.

The main technique is to substitute variables by linear functions. This way the function is restricted to an ane subspace of Fn. An ane disperser for sublinear dimension then guarantees that one can make n o(n) such substitutions before the function degenerates. It remains to show that each such substitution eliminates at least 3 gates from a circuit.

1 Introduction Proving lower bounds on the circuit complexity of explicitly dened Boolean functions is one of the most famous and dicult problems in theoretical computer science. Already in 1949 Shannon [1] showed by a counting argument that almost all Boolean functions have circuits of size (2n /n) only. Still, we have no example of an explicit function requiring super-linear circuit size. Moreover, only a few proofs of linear lower bounds are known. We review some of them is Sect. 3. The best lower bound 3n o(n) for the basis B2 was proved by Blum in 1984 [2], the current record lower bound 5n o(n) for the basis U2 = B2 \ {, } was given in 2002 by Iwama, Lachish, Morizumi, and Raz [3].

Research is partially supported by Federal Target Program “Scientic and scientic pedagogical personnel of the innovative Russia” 2009–2013, Russian Foundation for Basic Research, RAS Program for Fundamental Research, Grant of the President of Russian Federation (NSh-5282.2010.1), and PDMI Computer Science Club scholar ship.

– 133 – All bounds mentioned above are proved by the gate elimination method.

The main idea of this method is the following. One considers a Boolean function on n variables from a certain class of functions and shows that for any circuit computing this function setting some variables to constants yields a sub-function of the same type and eliminates several gates. Usually, a gate is eliminated just because one of its inputs becomes a constant. By induction, one concludes that the original circuit must have many gates. Though this method is essentially the only known method for proving non-trivial lower bounds for general circuit complexity, as many authors note it is unlikely that it will allow to prove non linear bounds.

In this paper, we prove a 3n O(d) lower bound on the circuit complexity of a Boolean function f : Fn F2 that is not constant on any ane subspace of Fn of dimension at least d. Such functions are called ane dispersers for dimension d. The proof of a lower bound is much simpler than the proof of the currently strongest lower bound 3n o(n) given by Blum in 1984 [2]. However, it is not easy to construct explicitly an ane disperser for small d. Only recently Ben-Sasson and Kopparty [4] presented a construction for sublinear d = o(n) (namely, d = (n4/5 )).

The main idea of the proof is as follows. Consider an ane disperser f for dimension d. We know that f is not constant on any ane subspace of Fn of dimension at least d. Hence for any I1,..., Ind {1,..., n} and c1,..., cnd F2, f is not constant on ane subspace {x Fn | xi = ck, for all 1 k n d} iIk of dimension at least d. We consequently nd substitutions of the form xik = iIk xi ck so that at least 3 gates are eliminated under each of them from the current circuit. This way we eliminate at least 3n O(d) gates.

To nd a substitution under which at least 3 gates are eliminated we just take the topologically rst non-linear gate R (i.e., a gate that does not compute iI xi c, for I {1, 2,..., n}, c F2 ) of a circuit.

a function of the form Since it is the rst such gate, both its inputs P and Q are linear functions. By an appropriate substitution, we make P constant which also makes R constant.

This kills P, R and all the successors of R, i.e., at least 3 gates in total. In the example given in Fig. 1, one can make a substitution x1 = x2 1. Then P evaluates to 0, R also evaluates to 0 and T is also eliminated. The formal proof is given in Section 4.

Similar ideas (substituting variables by linear functions) were used by Boyar and Peralta [5] for proving lower bounds on the multiplicative complexity of Boolean functions. The multiplicative complexity of a Boolean function is dened as the smallest number of gates in a circuit over {,, 1} computing this function. As with the circuit complexity, it is known [6] that the multiplicative complexity of almost all Boolean functions is about 2n/2, while the best known lower bound for an explicit function is n 1. As an easy consequence we obtain a lower bound n d 1 on the multiplicative complexity of an ane disperser for dimension d.

– 134 – x1 x2 x3 x P Q R T Fig. 1. Substitution x1 = x2 1 eliminates at least 3 gates from this circuit.

2 General Setting By Bn we denote the set of all Boolean functions f : Fn F2. A circuit over a basis B2 is a directed acyclic graph with nodes of in-degree 0 or 2. Nodes of in-degree 0 are marked by variables from {x1,..., xn } and are called inputs.

Nodes of in-degree 2 are marked by functions from and are called gates. There is also a special output gate where the result is computed. The size of a circuit is its number of gates. By C (f ) we denote the minimum size of a circuit over computing f. The two commonly studied bases are B2 and U2 = B2 \ {, }.

We call a function f B2 degenerate if it does not depend essentially on some of its variables, i.e., there is a variable xi such that the sub-functions f |xi =0 and f |xi =1 are equal. It is easy to see that a gate computing a degenerate function from B2 can be easily eliminated from a circuit without increasing its size (when eliminating this gate one may need to change the functions computed at its successors). The set B2 contains the following sixteen functions f (x, y):

– six degenerate functions: 0, 1, x, x 1, y, y 1;

– eight functions of the form ((x a)(y b)) c, where a, b, c F2 (throughout all the paper we write xy instead of x y);

we call them -type functions;

– two functions of the form x y a, where a F2 ;

these are called -type functions.

An example on simplifying a circuit is given in Fig. 2. We assign x2 the value 1. Then Q computes the constant 1, so P and hence also R compute x1 1. These 3 gates can be eliminated from the circuit. After that S computes (x1 1) x4, i.e., x1 x4, while T computes (x1 1)S. The negation sign on the wire from x1 to T is intended to reect the fact that the binary function computed at T is not just xy as in the picture, but (x 1)y.

Below we state several simple but important facts illustrated in this example.

– The substitution x2 = 1 trivializes the gate Q (i.e., makes it constant), so not only Q is eliminated, but also all its successors. At the same time, P is not trivialized, but becomes a degenerate function. This illustrates the dierence between - and -type gates and explains why currently best lower bounds for circuits over U2 are stronger than those for circuits over B2.

– 135 – x1 x2 x3 x1 x ¬ x4 S P Q S R T x2 = T Fig. 2. Example of simplifying a circuit under a substitution x2 = 1.

– While simplifying a circuit under a substitution one may need to change the functions computed at gates.

– The resulting circuit depends on neither x2 nor x3, though only x2 was substituted.

3 Known Lower Bounds Below we review some of the known lower bounds on circuit complexity and in each case indicate a property of a Boolean function that is important for the proof. We concentrate on the circuit size, while there are many other models such as formulas, branching programs, monotone circuits, constant-depth circuits, where functions with other interesting properties are needed. Note that apart from the properties described below, each function for which one would like to prove a lower bound by the gate elimination method must also satisfy the following natural property: it must remain essentially the same after replacing a variable by a constant.

– Bounds on CB • Schnorr [7] proved a 2n c lower bound on CB2 for a function satisfying the following property: for any two dierent input variables xi and xj, there are at least three dierent sub-functions among f |xi =0,xj =0, f |xi =1,xj =0, f |xi =0,xj =1, f |xi =1,xj =1.

This property is needed to argue that a top of a circuit cannot look like this:

xj xi That is, at least one of xi and xj must feed also some other gate (as otherwise one would get at most two dierent subfunctions w.r.t. xi and – 136 – xj ). One then assigns a constant to this variable and kills two gates. A 2n c lower bound follows by induction.

There are many natural functions satisfying this property. E.g., MODn, m,r for m 3, dened as follows:

n MODn (x1,..., xn ) = 1 i xi r (mod m).

m,r i= • Paul [8] proves a 2n o(n) lower bound on CB2 for the storage access function: for a Flog n and x Fn, f (a, x) = xa, where a is the number from {0,..., n 1} whose binary representation is a, and xa is the cor responding bit of a. An important property of this function is that for any input variable xi, when all the bits of a are already assigned, the output of f either equals xi or does not depend on xi at all. This allows to substitute xi not only by a constant, but by an arbitrary function.

• Stockmeyer [9] proved a 2.5nc lower bound on CB2 for many symmetric functions (in particular, for all MODn functions). He essentially uses m,r the fact that for symmetric functions substituting xi = h, xj = h 1 for a function h is the same as just saying that xi xj = 1.

• A function for which Blum [2] proved a 3n o(n) lower bound on CB (a similar function was also used by Paul [8]) is dened as follows. Let a, b, c Flog n, x Fn, p, q, r F2. Then f (a, b, c, p, q, r, x) = q((xa x) (px(xc r))) (1 q)(xa x).

b b b For any xi and xj, one can get xi xj as well as xi xj from f by assigning some of the remaining variables.

• Kojevnikov and Kulikov [10] proved a 7n/3 c lower bound for func tions with high multiplicative complexity. Any circuit computing such a function must have several -type gates. This allows to assign dierent weights to - and -type gates when counting the number of gates that are eliminated.

– Bounds on CU • Schnorr [7] proved a 3n c lower bound on CU2 for the parity function.

A property that helps here is that an optimal circuit cannot contain a variable of out-degree exactly 1. Indeed, if such a variable xi existed, one could substitute all the other variables to trivialize the unique gate fed by xi. This would make the function independent of xi, a contradiction.

• Zwick [11] proved a 4nc lower bound for all MODn functions, m 3.

m,r He noticed that any optimal circuit for such a function can contain only a constant number of out-degree 1 variables. This allows to remove such variables from the consideration by using a circuit complexity measure equal to the number of gates minus the number of out-degree 1 variables.

• Iwama, Lachish, Morizumi, and Raz [3] used Zwick’s circuit complexity measure to prove a lower bound 5n o(n) on CU2 for strongly two dependent functions, i.e., functions satisfying the following property: for – 137 – any two variables all the four sub-functions resulting by xing the values of these variables are dierent. This property guarantees that a top of a circuit cannot look like this:

xj xi This case is the main bottleneck in Zwick’s proof. An explicit construc tion of a strongly two-dependent function was previously given by Sav icky and Zak [12]. In fact, this function is even k-mixed, for k = no(n):

for any subset of k variables, all the 2k sub-functions w.r.t. these k vari ables are dierent. Recently, Amano and Tarui [13] showed that this property is not enough for proving stronger than 5n lower bounds on CU2 by constructing a function of circuit complexity 5n + o(n) that is k-mixed, for k = n o(n).

A 3n o(n) Lower Bound In this section we consider only circuits over B2. Let µ(C) = s(C) + N (C), where s(C) is the size (number of gates) of C and N (C) is the number of input variables of C with out-degree at least 1.

Lemma 1. Let P be a gate of a circuit C that is a -type gate that depends only on -type gates of out-degree 1 and variables. Then there is a variable xj and a (possibly empty) subset of variables I {1,..., n} \ {j} such that for any constant c F2, the substitution xj = iI xi c makes the gate P constant and reduces N (C) at least by 1.

iI xi xj c0 for some 1 j n, Proof. Clearly P computes a function I {1,... n} \ {j}, c0 F2. We analyse the eect of reducing C under the iI xi c, for c F2. Let S be the set of gates that P substitution xj = depends on. Clearly S contains at least |I| 1 gates (as iI xi c0 cannot be computed by less than |I| 1 gates). To simplify C under the substitution iI xi c, we eliminate the gate P (as it now computes the constant xj = c c0 ) and all its successors (as they now compute degenerate functions).

iI xi c. For this, we To reduce N (C) by 1, we need to replace xj by eliminate all the gates from S (they were needed only for computing P ) and add |I| 1 gates computing iI xi. We then use them instead of xj. Clearly, the resulting circuit outputs the same as the initial circuit for all x Fn such that xj = iI xi c.

An example of such simplication is given in Fig. 3 (I = {2, 3, 4, 5}, j = 1).

Theorem 1. Let f : Fn F2 be an ane disperser for dimension d, A be an ane subspace of Fn of dimension D, and C be a circuit with n inputs such that x A, C(x) = f (x). Then µ(C) 4(D d).

– 138 – x1 x2 x1 x2 x x4 x Q R x3 x x x1 = xi i= P Q R Fig. 3. Example of a linear substitution.

Proof. We prove the inequality by induction on D. The base case D d is trivial. Consider now the case D d + 1. Take a circuit C computing f on A with the minimal possible µ(C). Assume wlog that C does not contain degenerate gates (all such gates can be eliminated without increasing µ(C)). Note also that C cannot compute a linear function. Indeed, if C computed a function of the form iI xi c, then f would be constant on an ane space A = {x A: iI xi = c} of dimension at least D 1 d. Thus, C contains at least one -type gate.

In the following we nd a substitution of the form iI xi c under which C is reduced to C such that µ(C) µ(C ) + 4 and C(x) = C (x) for all x A = {x A: iI xi = c}. Since A has dimension at least D 1, we conclude by induction that µ(C) 4(D 1 d) + 4 = 4(D d). Note that any gate that becomes constant under such substitution cannot be an output gate, as otherwise C would compute a linear function.

Consider a topological order on all the gates of C and let P be the rst gate in this order that is not a -type gate of out-degree 1. Since it depends only on -type gates and input variables, functions computed at both inputs of P are of the form iI1 xi c1 and iI2 xi c2. Below we consider ve cases, Fig. shows all of them.

– Case 1. P is a -type gate of out-degree at least 2. Then it clearly computes iI xi c. By the lemma above, by making P a function of the form constant we reduce µ at least by 4.

– Case 2. P is an -type gate.

• Case 2.1. One of the inputs of P is a gate Q. Then Q is a -type gate.

By making Q the constant (as in the lemma) which trivializes P we kill P, Q, and all the successors of P. Also, N (C) is reduced at least by 1, hence µ is reduced at least by 4.

• Case 2.2. Both inputs of P are variables xi and xj and at least one of them (say, xi ) have out-degree at least 2. By assigning xi the constant which trivializes P we kill all the successors of xi and all the successors – 139 – xj xj xj xi xi xi Q P P P P P Q Case 1 Case 2.1 Case 2.2.1 Case 2.2.2 Case 2. Fig. 4. All cases of the proof of P. Clearly N (C) is reduced at least by 1. By considering two sub-cases we show that s(C) is reduced at least by 3.

Case 2.2.1. xi has a successor that is not fed by P. Then this successor is eliminated as well as P and all the successors of P.

Case 2.2.2. The only successor of P is the gate Q and it is also fed by xi. Then clearly it becomes constant (as both its inputs are constants) and so all its successors are also eliminated.

• Case 2.3. Both inputs of P are out-degree 1 variables xi and xj. By assigning xi the constant which trivializes P, we eliminate P and all its successors and reduce N (C) at least by 2. Hence µ is reduced at least by 4.

Corollary 1. Any circuit over B2 computing an ane disperser for dimension d has at least 3n 4d gates.

Proof. Indeed, by Theorem 1, for any circuit C computing an ane disperser for dimension d, s(C) = µ(C) N (C) 4(n d) N (C) 3n 4d.

Thus, an ane disperser for sublinear dimension requires circuits of size at least 3n o(n). It is also easy to see that by the same method one can prove a lower bound n o(n) on the multiplicative complexity of ane dispersers for sublinear dimension. For this, we just make n o(n) linear substitutions each time killing the rst -type gate.

5 Further Directions 1. It would be interesting to improve the presented lower bound by a more involved case analysis or to nd another property of Boolean functions im plying a stronger than 3n lower bound.

– 140 – 2. Another interesting direction is to prove a non-trivial upper bound for an ane disperser.

3. An (apparently) easier problem is to close one of the following gaps (see [9], [14], [11]):

2.5n c CB2 (MODn ) 3n + c, 4n c CU2 (MODn ) 5n + c.

Also it is still not known whether C(MODn ) is strictly greater than C(MODn ) p q for primes p q. Note however that any symmetric function can be com puted by a circuit (over B2 ) of size 4.5n + o(n) [14].

4. It would also be interesting to nd a Boolean function of multiplicative complexity at least cn, for a constant c 1.

6 Acknowledgements We would like to thank Edward A. Hirsch and Arist Kojevnikov as well as the anonymous referees for helpful comments and Arnab Bhattacharyya for pointing us out the paper [4].

References 1. Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Technical Journal 28 (1949) 59– 2. Blum, N.: A Boolean function requiring 3n network size. Theoretical Computer Science 28 (1984) 337– 3. Iwama, K., Lachish, O., Morizumi, H., Raz, R.: An explicit lower bound of 5n o(n) for boolean circuits. Unpublished manuscript. Available at http://www.wisdom.weizmann.ac.il/ranraz/publications/Podedl.ps (2005) 4. Ben-Sasson, E., Kopparty, S.: Ane dispersers from subspace polynomials. In:

Proceedings of the Annual Symposium on Theory of Computing (STOC). Volume 679., ACM Press (2009) 65– 5. Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theoretical Computer Science 396 (2008) 223– 6. Boyar, J., Peralta, R., Pochuev, D.: On The Multiplicative Complexity of Boolean Functions over the Basis (,, 1). Theoretical Computer Science 235(1) (2000) 1– 7. Schnorr, C.P.: Zwei lineare untere Schranken fr die Komplexitt Boolescher Funk u a tionen. Computing 13 (1974) 155– 8. Paul, W.J.: A 2.5n-lower bound on the combinational complexity of Boolean functions. SIAM Journal of Computing 6(3) (1977) 427– 9. Stockmeyer, L.J.: On the combinational complexity of certain symmetric Boolean functions. Mathematical Systems Theory 10 (1977) 323– 10. Kojevnikov, A., Kulikov, A.S.: Circuit Complexity and Multiplicative Complexity of Boolean Functions. In: Proceedings of Computability in Europe (CiE). Volume 6158 of Lecture Notes in Computer Science., Springer (2010) 239– – 141 – 11. Zwick, U.: A 4n lower bound on the combinational complexity of certain symmetric boolean functions over the basis of unate dyadic Boolean functions. SIAM Journal on Computing 20 (1991) 499– 12. Savicky, P., Zak, S.: A large lower bound for 1-branching programs. Technical Report TR96-036, ECCC (1996) 13. Amano, K., Tarui, J.: A well-mixed function with circuit complexity 5n ± o(n):

Tightness of the Lachish-Raz-type bounds. In: Proceedings of Theory and Appli cations of Models of Computation. Volume 4978 of Lecture Notes in Computer Science., Springer (2008) 342– 14. Demenkov, E., Kojevnikov, A., Kulikov, A.S., Yaroslavtsev, G.: New upper bounds on the Boolean circuit complexity of symmetric functions. Information Processing Letters 110(7) (2010) 264– – 142 – Optimal Acceptors and Optimal Proof Systems Edward A. Hirsch Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St. Petersburg 191023, Russia http://logic.pdmi.ras.ru/~ hirsch/ Abstract. Unless we resolve the P vs NP question, we are unable to say whether there is an algorithm (acceptor ) that accepts Boolean tautologies in polynomial time and does not accept non-tautologies (with no time restriction). Unless we resolve the co -NP vs NP question, we are unable to say whether there is a proof system that has a polynomial-size proof for every tautology.

In such a situation, it is typical for complexity theorists to search for “universal” objects;

here, it could be the “fastest” acceptor (called opti mal acceptor ) and a proof system that has the “shortest” proof (called optimal proof system) for every tautology. Neither of these objects is known to the date.

In this survey we review the connections between these questions and generalizations of acceptors and proof systems that lead or may lead to universal objects.

1 Introduction and Basic Denitions Given a specic problem, does there exist the “fastest” algorithm for it? Does there exist a proof system possessing the “shortest” proofs of the positive in stances of the problem? Although the rst result in this direction was obtained by Levin [Lev73] in 1970s, these important questions are still open for most interesting languages, for example, the language of propositional tautologies.


Classical version of the problem. According to Cook and Reckhow [CR79], a proof system is a polynomial-time mapping of all strings (“proofs”) onto “the orems” (elements of a certain language L;

if L = TAUT is the language of all propositional tautologies, the system is called a propositional proof system).

The existence of a polynomially bounded propositional proof system (that is, a system that has a polynomial-size proof for every tautology) is equivalent to NP = co -NP. In the context of polynomial boundedness, a proof system can be equivalently viewed as a function that, given a formula and a “proof”, veries in polynomial time that the formula is a tautology: it must accept at least one “proof” for each tautology (completeness) and reject all proofs for non-tautologies (soundness).

Partially supported by RFBR grant 08-01-00640, the president of Russia grant “Leading Scientic Schools” NSh-5282.2010.1, and by Federal Target Programme “Scientic and scientic-pedagogical personnel of the innovative Russia” 2009–2013.

J. Kratochvil et al. (Eds.): TAMC 2010, LNCS 6108, pp. 28–39, 2010.

c Springer-Verlag Berlin Heidelberg – 143 – Optimal Acceptors and Optimal Proof Systems One proof system w is simulated by another one s if the shortest proof for every tautology in s is at most polynomially longer than its shortest proof in w. The notion of p-simulation is similar, but requires also a polynomial-time computable function for translating the proofs from w to s. A (p-)optimal propositional proof system is one that (p-)simulates all other propositional proof systems.

The existence of an optimal (or p-optimal) proof system is a major open ques tion for many languages including TAUT. Optimality would imply p-optimality for any system and any language if and only if the natural proof system for SAT (satisfying assignments) is p-optimal;

the existence of optimal system would imply the existence of p-optimal system if there is some p-optimal system for SAT [BKM09a]. If an optimal system for TAUT existed, it would allow one to reduce the NP vs co -NP question to proving proof size bounds for just one proof system. It would also imply the existence of a complete disjoint NP pair [Raz94, Pud03]. The existence of a p-optimal system for quantied Boolean for mulas would imply a complete language in NP co -NP [Sad97]. (See [BS09] regarding the situation for other languages and complexity classes.) Unfortu nately, no concise widely believed structural assumptions (like NP = co -NP) are known to imply the (non-)existence of (p-)optimal proof systems. Krajcek and Pudlk [KP89] showed that the existence is implied by NE = co -NE (resp., a E = NE) for optimal (resp., p-optimal) propositional proof systems, and Kbler, o Messner, and Torn [KMT03] weakened these conjectures to doubly exponential a time, but these conjectures are not widely believed.

An acceptor for a language L is a semidecision procedure, i.e., an algorithm that answers 1 for x L and does not stop for x L. An acceptor O is optimal / if for any other (correct) acceptor A, for every x L, the acceptor O stops on x in time bounded by a polynomial in |x| and the time taken by A(x). (In [KP89] optimal acceptors are called p-optimal algorithms;

the term “acceptor” was later introduced by Messner in his PhD thesis). Krajcek and Pudlk [KP89] showed a that for TAUT the existence of a p-optimal system is equivalent to the existence of an optimal acceptor. Then Sadowski [Sad99] proved a similar equivalence for SAT. Finally, Messner [Mes99] gave a dierent proof of these equivalences ex tending them to many other languages. We review these results in Section 3.

Monroe [Mon09] recently formulated a conjecture implying that such an algo rithm does not exist1. Note that Levin [Lev73] showed that an optimal algorithm does exist for nding witnesses for SAT (equivalently, for non-tautologies): just run all algorithms in parallel and stop as soon as one of them returns a sat isfying assignment. However, this procedure gives an optimal acceptor neither for TAUT nor for SAT, because (1) on tautologies, it simply does not stop;

(2) Levin’s algorithm enumerates search algorithms, and for an acceptor we need decision algorithms, which may be faster for some inputs;

the search-to-decision More precisely, if an optimal acceptor for TAUT exists, then there is an acceptor for BH (where BH = {(M, x, 1t ) | nondeterministic Turing machine M accepts x in t steps}) that works in time polynomial in t for every particular (M, x) such that M does not stop on x.

– 144 – 30 E.A. Hirsch reduction adds a lot to the running time by running the decision algorithm for shorter formulas as well, which may be surprisingly much larger than for the original input.

A proof system is automatizable if it has an automatization procedure that works in time bounded by a polynomial in the output length. This procedure A, given a “theorem”, outputs its (correct) proof for of length polynomially bounded by the length of the shortest proof for. It is easy to see that such a proof system can be easily turned into an acceptor with running time polyno mially related to the proof size and the input size. Vice versa, an acceptor can be converted into an automatizable proof system, where the proof is just the number of steps (written in unary) that the acceptor makes before accepting its input. Thus, in the classical case there is no dierence between acceptors and automatizable proof systems.

Extensions that give optimality. An obvious obstacle to constructing an optimal proof system or an optimal acceptor by enumeration is that no ecient proce dure is known for enumerating the set of all complete and sound proof systems (resp., acceptors). Recently, similar obstacles were overcome in other settings by considering either computations with non-uniform advice (see [FS06] for a survey) or heuristic algorithms [FS04, Per07, Its09]. In particular, (p-)optimal proof systems (and acceptors) with advice do exist [CK07], and we review this fact in Section 4.

As to heuristic computations, the situation is more complex. Recently, it was proved [HI10] that an optimal randomized heuristic acceptor does exist. However, in the heuristic case we lack the equivalence between optimal proof systems and optimal acceptors, and even the equivalence between acceptors and automatiz able proof systems is not straightforward. We review the heuristic case (including more recent directions) in Section 5.

Another possibility to obtain optimal proof systems is to generalize the notion of simulation. Recently, Pitassi and Santhanam [PS10] suggested a notion of “eective simulation” and constructed a proof system for quantied Boolean formulas that eectively simulates all other proof systems for QBF. We do not review this result here.

We conclude the paper by listing open questions in Section 6.

We now continue to Section 2 listing trivial facts that we will use in what follows.

2 Trivia Enumeration. Almost all constructions used in this survey employ the enumera tion of all Turing machines of certain kind. Some remarks regarding this follow.

First of all, recall that deterministic Turing machines (either decision ma chines that say yes/no, or transducers that compute arbitrary functions) can be eciently enumerated by their Gdel numbers and simulated with only a o polynomial overhead in time.

– 145 – Optimal Acceptors and Optimal Proof Systems For a recursively enumerable language, one can enumerate acceptors only by running the semidecision procedure in parallel.

Also one can require, if necessary, that the construction of each machine (we will need it for proof systems) includes an “alarm clock” that interrupts the machine after a certain number of steps.

Each proof system is p-simulated by another proof system where (x, w) runs in time, say, 100(|x| + |w|)2 : just pad the proofs appropriately;

the simulation omits the padding.

These facts allow us to limit ourselves to enumerating proof systems with quadratic alarm clock.

Frequently, we write that we execute “in parallel” a large (sometimes innite) number of computations. In reality this is achieved, of course, sequentially by alternating consecutive steps of these computations (for example, simulating the step k of the i-th machine at step (1 + 2k) · 2i, as in Levin’s optimal algorithm).

Acceptors and proof systems for subsets. For recursively enumerable L, for every acceptor A for L L there is an acceptor A for L that is almost as ecient on L as A. Similarly, for every proof system for L L there is a proof system for L that has the same proofs on L as.

Proofs vs candidate proofs. In what follows we call w a -proof of x if (x, w) = 1. Sometimes we write “u is a candidate -proof of x” to emphasize that u is intended for checking with (while it is not yet known whether (x, u) = 1).

3 Optimal Acceptors Exist i p-Optimal Proof Systems Exist 3.1 Krajcek-Pudlk’s Proof a In this section we give the proof by Krajcek and Pudlk [KP89]. The original a exposition demonstrates the equivalence of many statements, while we need only two and show only the required implications.

Theorem 1 ([KP89]). Optimal acceptors for TAUT exist i p-optimal proof systems for TAUT exist. Moreover, the suciency () holds for any language, not just TAUT.

Proof.. A candidate proof of x for our p-optimal proof system contains a description of a proof system (i.e., a deterministic Turing machine given by its Gdel number and equipped with a quadratic alarm clock) and a candidate o -proof. To verify the proof, (x, (, )) simply simulates (x, ) ensuring that accepts and then veries the correctness of by querying the optimal acceptor A for the statement y {0, 1}|x| {0, 1}|| z {0, 1}|x| ((y, ) = 0 y[z] = 0) written as a Boolean formula (here y[z] denotes the result of substituting the consecutive bits of z for the consecutive variables of the Boolean formula y).


– 146 – 32 E.A. Hirsch Since for every there is an algorithm that, given |x| and ||, writes such statement in time polynomial in |x| + ||, A must stop in (specic) polynomial time for specic (correct), which proves that p-simulates.

. The optimal acceptor A just applies in parallel all deterministic trans ducers hoping one of them outputs a -proof and lets verify the result.

Once returns 1, the acceptor A stops.

Since every acceptor A is a particular case of a proof system, there is a polynomial-time algorithm that, given tautology x, outputs -proofs in time polynomial in |x| and time spent by A on x.

Remark 1. Sadowski [Sad07] explains that there exist an optimal automatizable proof system for TAUT i there is a (deterministic) acceptor that is optimal for non-deterministic acceptors as well.

3.2 Messner’s Proof Messner [Mes99] generalized the result of Krajcek and Pudlk to a wider class of a languages. His proof is also interesting even in the TAUT case, because it replaces the statement about the correctness of a proof system on all inputs of certain size by the statement about the correctness of a single proof of a single input.

Denition 1 ([BH77]). A language L is paddable if there is an injective non length-decreasing polynomial-time padding function padL : {0, 1} {0, 1} {0, 1} that is polynomial-time invertible on its image and such that for every x and w, x L padL (x, w) L.

Theorem 2 ([Mes99]). For every paddable r.e. language L, optimal acceptors for L exist i p-optimal proof systems for L exist.

Proof.. Similarly to Krajcek-Pudlk’s proof, a candidate proof for our p a optimal proof system contains a description of a proof system (with a quadratic alarm clock) and a candidate -proof, and (x, (, )) starts the verication by simulating (x, ). What makes a dierence is how veries the correctness of.

One could simulate the optimal acceptor A on x restricting its running time to a certain polynomial of |x| + ||. However, there is no warranty that this amount of time is enough for A. Therefore, we run it on a dierent input where A is guaranteed to run in polynomial time and certies the correctness of the proof. Namely, we run it on padL (x, ). By the denition of padL, the result is 1 i x L. For a correct proof, this result is output in a polynomial time because for a correct system, the set {padL (x, ) | x L, (x, ) = 1} L can be accepted in a polynomial time (the polynomial is the sum of the time spent by pad1 and by ), and A is an optimal acceptor.

L. See Theorem 1.

– 147 – Optimal Acceptors and Optimal Proof Systems 4 Non-uniform Advice Gives Optimal Proof Systems Cook and Krajcek [CK07] show that allowing one bit of non-uniform advice yields a p-optimal proof system (against simulations with advice). A similar result for acceptors is not known.

Denition 2. A proof system with t(n) bits of advice is a polynomial-time al gorithm (x, w, ) and a sequence (n )nN, where n {0, 1}t(n), such that for all x, x L w (x, w, |x|+|w| ) = 1.

Theorem 3 ([CK07], see also [BKM09b]). For every language L, there is a proof system with 1 bit of advice that simulates every proof system with k(n) = O(log n) bits of advice. Moreover, the simulation can be computed in polynomial time with k(n) bits of advice.

Proof. A candidate proof for the constructed proof system contains a de scription of a proof system (a deterministic Turing machine given by its Gdel number and equipped with a quadratic alarm clock) written in unary as o 1, a candidate -proof, and an advice string {0, 1}k(n) written in unary as a string 1 of length 2k(n). Then (x, (1,, 1 )) starts the verication by simulating (x,, ). To verify the correctness of, the system simply queries its advice bit, which is supposed to say whether with advice string is correct on all candidate theorems of size |x| and proofs of size ||. To en sure that this is the same bit for all couples (x, (1,, 1 )) of the same size, we must choose pairing function such that for all strings a1, a2, a3, a4, b1, b2, b3, b4, for each i, |ai | = |bi | |(a1, (a2, a3, a4 ))| = |(b1, (b2, b3, b4 ))|.

The simulation can be computed trivially.

Remark 2. One may suppose that, similarly to the classical case, the existence of optimal proof systems with advice implies the existence of disjoint NP pairs with advice. This is indeed the case;

however, in order to keep the closedness under reductions (with advice) the advice given must have length O(1) and not a specic constant number of bits. For exactly one bit of advice one gets only an NP pair that is hard for disjoint NP without advice under many-one reductions without advice [BS09].

5 Heuristic Case: Optimal Acceptors Exist, Hope for Proof Systems Hirsch and Itsykson [HI10] introduced heuristic2 acceptors (called heuristic au tomatizers in [HI10]) and heuristic proof systems. Heuristic algorithms (see, e.g., All heuristic computations that we consider are randomized. Therefore, we omit the word “randomized” from the terms that we introduce and mention it explicitly only in the denitions. However, it is possible to consider deterministic heuristic acceptors and proof systems as well.

– 148 – 34 E.A. Hirsch [BT06]) are algorithms that make errors for a small amount of inputs. Similarly, heuristic proof systems claim a small amount of wrong “theorems”.

Since we are interested in the behaviour only on the positive instances (“the orems”), our denition of a distributional problem is dierent from the usual denition used for heuristic algorithms. Formally, we have a probability distribu tion concentrated on non-theorems and require that the probability of sampling a non-theorem accepted by an algorithm or validated by a proof system is small.

Denition 3. We call a pair (D, L) a distributional proving problem if D is a collection of probability distributions Dn concentrated on L {0, 1}n.

In what follows we write PrxDn to denote the probability taken over x from such distribution, while PrA denotes the probability taken over internal random coins used by algorithm A.

5.1 Heuristic Acceptors Denition 4. A heuristic acceptor for distributional proving problem (D, L) is a randomized algorithm A with two inputs x {0, 1} and d N that satises the following conditions:

1. A either outputs 1 (denoted A(...) = 1) or does not halt at all;

2. For every x L and d N, A(x, d) = 1.

3. For every n, d N, 1 Pr{A(r, d) = 1} Pr.

8 d rDn A (In fact, the specic constant is not important.) Remark 3. Similarly to the classical case, for recursively enumerable L, condi tions 1 and 2 can be easily enforced at the cost of a slight overhead in time by running L’s semidecision procedure in parallel.

Given the denition of heuristic acceptor, we now adapt the classical notions of simulation and optimality to the heuristic case and give related basic facts. In what follows, all acceptors are for the same problem (D, L).

Denition 5. The time spent by heuristic acceptor A on input (x, d) is dened as the median time tA (x, d) = min t N Pr{A(x, d) stops in time at most t}.

A Denition 6. Heuristic acceptor S simulates heuristic acceptor W if there are polynomials p and q such that for every x L and d N, tS (x, d) p(tW (x, d ) · |x| · d).

max d q(d·|x|) An optimal heuristic acceptor is one that simulates every heuristic acceptor.

– 149 – Optimal Acceptors and Optimal Proof Systems Denition 7. Heuristic acceptor A is polynomially bounded if there is a poly nomial p such that for every x L and every d N, tA (x, d) p(d · |x|).

The following proposition follows directly from the denitions.

Proposition 1. If W is polynomially bounded and is simulated by S, then S is polynomially bounded too.

2. An optimal heuristic acceptor is not polynomially bounded if and only if no heuristic acceptor is polynomially bounded.

Remark 4 (I.Monakhov). If one-way functions exist, then there is a polynomial time samplable distribution D such that (D, TAUT) has no polynomially bounded heuristic acceptor.

Theorem 4 ([HI10]). Let (D, L) be a distributional proving problem, where L is recursively enumerable and D is polynomial-time samplable, i.e., there is a polynomial-time randomized Turing machine that given 1n on input outputs x with probability Dn (x) for every x {0, 1}n. Then there exists an optimal heuristic acceptor for (D, L).

Proof (sketch). The construction consists of three procedures.

The rst one, Test, estimates the probability of error of a candidate acceptor A on a given input by repeating A and counting its errors, it accepts if the number of errors is above certain threshold.

The second one, Certify, makes sure that the outermost probability in the correctness condition of a candidate acceptor A is small enough by repeating A at randomly sampled inputs of prescribed size, and counting errors reported by Test.

Finally, the optimal acceptor U, given x and d, runs the following processes for i {1,..., l(n)}, where l(n) is any slowly growing function, in parallel:

1. For certain d, run Ai (x, d ), the algorithm with Gdel number i satisfying o conditions 1 and 2 of Def. 4, and compute the number of steps Ti made by it before it stops.

2. If Certify accepts Ai executed on inputs of size |x| for at most Ti steps, then output 1 and stop U (all processes).

If none of the processes has stopped, U goes into an innite loop.

5.2 Heuristic Proof Systems Denition 8. Randomized Turing machine is a heuristic proof system for distributional proving problem (D, L) if it satises the following conditions.

1. The running time of (x, w, d) is bounded by a polynomial in d, |x|, and |w|.

– 150 – 36 E.A. Hirsch 2. (Completeness) For every x L and every d N, there exists a string w such that Pr{(x, w, d) = 1} 1. Every such string w is called a correct (d) -proof of x.

3. (Soundness) PrxDn {w : Pr{(x, w, d) = 1} 1 } d.

Unfortunately, we cannot prove the equivalence between acceptors and proof systems in the heuristic case. Therefore, we focus our attention on automatizable heuristic proof systems. Surprisingly, even the equivalence between acceptors and automatizable proof systems is not straightforward in this case.

In [HI10], a heuristic automatizable proof system is dened straightforwardly, and it is shown that it necessarily denes an acceptor taking time at most poly nomially larger than the length of the shortest proof in the initial system. This shows that heuristic acceptors form a more general notion than automatizable heuristic proof systems. Neither the converse nor the existence of an optimal automatizable heuristic proof system is shown in [HI10].

However, for a relaxed denition presented below, the equivalence does take place. (The proof of this statement is not published yet [HIS10], so you should take it with a bunch of salt for now.) In particular, there exists a p-optimal system in the class of heuristic automatizable proof systems.

Denition 9. Heuristic proof system is automatizable if there is a randomized Turing machine A satisfying the following conditions.

1. For every x L and every d N, there is a polynomial p such that |w| p(d · |x| · |w |) Pr{(x, w, d) = 1} 1, Pr (1) 4 wA(x,d) where w is the shortest correct (d) -proof of x.

2. The running time of A(x, d) is bounded by a polynomial in |x|, d, and the size of its own output.

Remark 5. 1. This denition is dierent from one in [HI10].

2. We do not require the algorithm A to generate correct proofs. It suces to generate “quasi-correct” (such that Pr{(x, w, d) = 1} 1 ) with probability 4. At present, we are unable to construct an optimal system or to show the equivalence to heuristic acceptors if 1 is strengthened to 1 as in [HI10].

4 Denition 10. We say that heuristic proof system 1 simulates heuristic proof system 2 if there exist polynomials p and q such that for every x L, the (d) shortest correct 1 -proof of x has size at most (d ) p(d · |x| · {the size of the shortest correct max -proof of x}). (2) d q(d·|x|) We say that heuristic proof system 1 p-simulates3 heuristic proof system 2 if 1 simulates 2 and there is a polynomial-time (deterministic) algorithm that The denition we give here may be too restrictive: it requires a deterministic algo rithm that is given a proof for specic d = q(d · |x|). It works for our purposes, but can be relaxed.

– 151 – Optimal Acceptors and Optimal Proof Systems q(d·|x|) (d) converts a 2 -proof into a 1 -proof of size at most (2) such that the probability to accept a new proof is no smaller than the probability to accept the original one.

Denition 11. Heuristic proof system is polynomially bounded if there ex ists a polynomial p such that for every x L and every d N, the size of the shortest correct (d) -proof of x is bounded by p(d · |x|).

Proposition 2. If heuristic proof system 1 simulates system 2 and 2 is polynomially bounded, then 1 is also polynomially bounded.

We now show how heuristic acceptors and automatizable heuristic proof systems are related.

Consider automatizable proof system (, A) for distributional proving prob lem (D, L) with recursively enumerable language L. Let us consider the following algorithm A (x, d):

1. Execute 1000 copies of A(x, d) in parallel.

For each copy, (a) if it stops with result w, then – execute (x, w, d) 60000 times;

– if there were at least 10000 accepts of (out of 60000), stop all parallel processes and output 1.

2. Execute the enumeration algorithm for L;

output 1 if this algorithm says that x L;

go into an innite loop otherwise.

Proposition 3. If (, A) is a (correct) heuristic automatizable proof system for recursively enumerable language L, then A is a (correct) heuristic acceptor for x L and tA (x, d) is bounded by polynomial in the size of the shortest correct (d) -proof of x.

The proof is a routine application of Cherno bounds, and we skip it. The converse statement is also true. The construction of automatizable heuristic proof system (, A) made from heuristic acceptor B is as follows.

A(x, d):

1. Run B(x, d).

2. If B(x, d) = 1, output 1T, where T is the total number of steps made by B.

(x, w, d):

1. Run B(x, d).

2. If B makes less than |w| steps and outputs a 1, accept. Otherwise, reject.

Theorem 5. (, A) is an automatizable heuristic proof system. For every x L, the length of the shortest -proof is upper bounded by the (median) running time of B.

Corollary 1 (optimal automatizable heuristic proof system). There is an automatizable heuristic proof system that p-simulates every automatizable heuristic proof system.

– 152 – 38 E.A. Hirsch 6 Open Questions Classical systems. It is still unknown whether (p-)optimal propositional proof systems exist. No concise widely believed structural assumption (such as NP = co -NP) is known to imply their nonexistence.

Acceptors with advice. Construct an optimal acceptor with short non-uniform advice either by extending the equivalence between optimal acceptors and p optimal proof systems or directly. The main obstacle here is the dierence be tween proof systems with “input advice” (as dened above) and proof systems with “output advice” (where an advice string corresponds to the length of input x, not proof w). However, [BKM09b] shows that for propositional proof sys tems with logarithmic advice, these cases are equivalent w.r.t. the polynomial boundedness.

Heuristic systems. It is challenging to extend the equivalence between optimal acceptors and p-optimal proof systems to the heuristic case, as it would give an optimal heuristic system.

It would be interesting to strengthen the automatizability condition for heuris tic systems by requiring to output real proofs (i.e., replace the innermost prob ability 1 by 1 ) without losing the equivalence to heuristic acceptors.

4 It would also be interesting to suggest a notion of a heuristic disjoint NP pair and show the existence of a complete pair.

Acknowledgements The author is very grateful to Olaf Beyersdor, Dmitry Itsykson, Hunter Monroe, Sergey Nikolenko, Natalia Tsilevich, Zenon Sadowski, and Alexander Smal for valuable comments, and to all participants of the proof complexity seminar in PDMI in September–December 2009 for numerous discussions on the topic.

References [BH77] Berman, L., Hartmanis, J.: On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing 6(2), 305–322 (1977) [BKM09a] Beyersdor, O., Kbler, J., Messner, J.: Nondeterministic functions and o the existence of optimal proof systems. Theor. Comput. Sci. 410(38-40), 3839–3855 (2009) [BKM09b] Beyersdor, O., Kbler, J., Mller, S.: Nondeterministic instance complex o u ity and proof systems with advice. In: Dediu, A.H., Ionescu, A.M., Martn Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 164–175. Springer, Hei delberg (2009) [BS09] Beyersdor, O., Sadowski, Z.: Characterizing the existence of optimal proof systems and complete sets for promise classes. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol. 5675, pp.

47–58. Springer, Heidelberg (2009) [BT06] Bogdanov, A., Trevisan, L.: Average-case complexity. Foundation and Trends in Theoretical Computer Science 2(1), 1–106 (2006) – 153 – Optimal Acceptors and Optimal Proof Systems Cook, S.A., Krajcek, J.: Consequences of the provability of N P P/poly.

[CK07] The Journal of Symbolic Logic 72(4), 1353–1371 (2007) [CR79] Cook, S.A., Reckhow, R.A.: The relative eciency of propositional proof systems. The Journal of Symbolic Logic 44(1), 36–50 (1979) [FS04] Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polyno mial time. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 316–324 (2004) [FS06] Fortnow, L., Santhanam, R.: Recent work on hierarchies for semantic classes. SIGACT News 37(3), 36–54 (2006) [HI10] Hirsch, E.A., Itsykson, D.: On optimal heuristic randomized semidecision procedures, with application to proof complexity. In: Proceedings of STACS 2010, pp. 453–464 (2010) [HIS10] Hirsch, E.A., Itsykson, D., Smal, A.: Optimal heuristic randomized ac ceptors and automatizable proof systems (March 2010) (unpublished manuscript) [Its09] Itsykson, D.M.: Structural complexity of AvgBPP. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol. 5675, pp.

155–166. Springer, Heidelberg (2009) [KMT03] Kbler, J., Messner, J., Torn, J.: Optimal proof systems imply complete o a sets for promise classes. Inf. Comput. 184(1), 71–92 (2003) [KP89] Krajcek, J., Pudlk, P.: Propositional proof systems, the consistency of a rst order theories and the complexity of computations. The Journal of Symbolic Logic 54(3), 1063–1079 (1989) [Lev73] Levin, L.A.: Universal sequential search problems. Problems of Informa tion Transmission 9, 265–266 (1973) (in Russian);

English translation in:



Pages:     | 1 | 2 || 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.