Сводимости систем доказательств

Гаевой Никита Сергеевич
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Задача существования p-оптимальной пропозициональной системы доказательств является одной из центральных открытых проблем сложности доказательств.

Цель данной работы заключается в изучении частного случая этой задачи, а именно, случая сильных сведений. Мы также вводим понятие ограниченной системы доказательств и изучаем связь между оптимальностью и автоматизируемостью для ограниченных систем доказательств.

1 Introduction 1
2 Definitions and the unbounded case 2
3 The structure of hard instances 5
4 Optimality under monotone simulations 6
5 Optimality under AC0 -simulations 7

The notion of a propositional proof system is a central notion of proof complexity. The classical version of the definition of a proof system by Cook and Reckhow [CR79] is a polynomial-time mapping of all strings (“proofs”) onto “theorems” that are elements of a certain language L. If the language of theorems is the language of all propositional tautologies TAUT, then the proof system is called a propositional proof system. A propositional proof system is polynomially bounded if it has a polynomial size proof for every tautology. The problem of the existence of a polynomially bounded proposi- tional proof system is the fundamental problem of proof complexity and it is equivalent to the problem of the equality of classes NP and coNP. A propo- sitional proof system can also be equivalently defined as a polynomial-time function that takes a formula and a string and verifies whether the given string is a valid proof of the given formula. In order to be a valid proof system such a function should accept at least one string for each tautology (completeness) and reject all strings for all other formulas (soundness). The latter definition is more convenient for working with simulations, so we will use it throughout the entire work.
Similarly to the languages in complexity classes, propositional proof sys- tems also have notions for “reduction”. A proof system Π simulates another proof system Φ if for every tautology the size of its shortest Π-proof is at most polynomially longer than the size of the shortest Φ-proof. However, we are mostly interested in a stronger notion of p-simulation that additionally requires the existence of a polynomial-time mapping of all Π-proofs into Φ- proofs (the mapping can also access the tautology). The second major open problem in proof complexity is the problem of the existence of an optimal (p-optimal) proof system, thats it, a system that simulates (p-simulates) any other proof system. The existence of the optimal propositional proof system
would not only reduce the problem NP =? coNP to proving proof size bounds for just one proof system, but also imply the existence of a complete disjoint NP pair [Raz94; Pud01].
1
Unfortunately, there is no known correspondence between the problem of the existence of an (p-)optimal proof system and any structural assumptions
(like NP =? coNP for the problem of the existence of a polynomially bounded proof system). Kraj ́ıˇcek and Pudla ́k [KP89] showed that the existence of an optimal (respectively, p-optimal) propositional proof system follows from the assumption NE = coNE (respectively, E = NE) and K ̈obler, Messner and Tor ́an [KMT03] weakened these conjectures to double exponential time, however, the converse implication is not known nor widely believed.
A proof system is automatizable if it has an algorithm that, given a tautology, is able to produce its proof in a time polynomial in the length of the shortest proof. Automatizability seems to be quite a restrictive trait of a proof system, that is, for many proofs systems it is known that they are not automatizable unless P = NP [AM20; de +20; G ̈o ̈o+20; Gar20]. However, it is not known whether optimal proof systems (if they exist) can be automatizable.
Since the problem of the existence of (p-)optimal proof system is seem- ingly hard, it is also interesting to consider its extended or restricted cases. Cook and Kraj ́ıˇcek showed that optimal proof systems with non-uniform ad- vice exist and that even one bit of advice per proof length is sufficient to p-simulate all classical propositional proof systems [CK07]. Another way to extend the problem is to generalize the notion of p-simulation. The most prominent example of this approach is the notion of effective simulation in- troduced by Pitassi and Santhanam [PS10].
In this work we focus on another special case of the problem. We in- troduce a notion of C-simulation, a specialized version of p-simulation, for certain classes of circuits C and study the problem of the existence of C- optimal propositional proof systems (i.e. systems that C-simulate any other propositional proof system). In Section 2 we provide a positive result for this problem: the existence of p-optimal proof systems implies the existence of C-optimal proof systems for any reasonable class C. Then, we introduce a notion of a bounded proof system and dedicate Sections 4 and 5 to negative results. These results state that no efficiently bounded C-optimal (where C stands for monotone and AC0-circuits, respectively) proof system could exist unless there exists an automatizable optimal proof system. Informally, it means that simulating other systems in C-optimal proof system using only efficient proofs is almost as hard as automatizing.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

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

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Татьяна П. МГУ им. Ломоносова 1930, выпускник
    5 (9 отзывов)
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по и... Читать все
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по истории. Увлекаюсь литературой и темой космоса.
    #Кандидатские #Магистерские
    11 Выполненных работ
    user1250010 Омский государственный университет, 2010, преподаватель,...
    4 (15 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    21 Выполненная работа
    Егор В. кандидат наук, доцент
    5 (428 отзывов)
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Ск... Читать все
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Скорее всего Ваш заказ будет выполнен раньше срока.
    #Кандидатские #Магистерские
    694 Выполненных работы
    Кирилл Ч. ИНЖЭКОН 2010, экономика и управление на предприятии транс...
    4.9 (343 отзыва)
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). С... Читать все
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). Сейчас пишу диссертацию на соискание степени кандидата экономических наук.
    #Кандидатские #Магистерские
    692 Выполненных работы
    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Алёна В. ВГПУ 2013, исторический, преподаватель
    4.2 (5 отзывов)
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическо... Читать все
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическое образование. В данный момент работаю преподавателем.
    #Кандидатские #Магистерские
    25 Выполненных работ
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ
    Антон П. преподаватель, доцент
    4.8 (1033 отзыва)
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публик... Читать все
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публикуюсь, имею высокий индекс цитирования. Спикер.
    #Кандидатские #Магистерские
    1386 Выполненных работ

    Другие учебные работы по предмету

    Кооперативные игры на гиперграфах
    📅 2019год
    🏢 Санкт-Петербургский государственный университет