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

Гаевой Никита Сергеевич
Бесплатно
В избранное
Работа доступна по лицензии 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 экспертов уже готовы начать работу над твоим проектом!

    Елена С. Таганрогский институт управления и экономики Таганрогский...
    4.4 (93 отзыва)
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на напис... Читать все
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на написании курсовых и дипломных работ, а также диссертационных исследований.
    #Кандидатские #Магистерские
    158 Выполненных работ
    Дарья Б. МГУ 2017, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Дарья С. Томский государственный университет 2010, Юридический, в...
    4.8 (13 отзывов)
    Практикую гражданское, семейное право. Преподаю указанные дисциплины в ВУЗе. Выполняла работы на заказ в течение двух лет. Обучалась в аспирантуре, подготовила диссерт... Читать все
    Практикую гражданское, семейное право. Преподаю указанные дисциплины в ВУЗе. Выполняла работы на заказ в течение двух лет. Обучалась в аспирантуре, подготовила диссертационное исследование, которое сейчас находится на рассмотрении в совете.
    #Кандидатские #Магистерские
    18 Выполненных работ
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ
    Екатерина С. кандидат наук, доцент
    4.6 (522 отзыва)
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    #Кандидатские #Магистерские
    1077 Выполненных работ
    Александр Р. ВоГТУ 2003, Экономический, преподаватель, кандидат наук
    4.5 (80 отзывов)
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфин... Читать все
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфинансы (Казначейство). Работаю в финансовой сфере более 10 лет. Банки,риски
    #Кандидатские #Магистерские
    123 Выполненных работы
    Дмитрий К. преподаватель, кандидат наук
    5 (1241 отзыв)
    Окончил КазГУ с красным дипломом в 1985 г., после окончания работал в Институте Ядерной Физики, защитил кандидатскую диссертацию в 1991 г. Работы для студентов выполня... Читать все
    Окончил КазГУ с красным дипломом в 1985 г., после окончания работал в Институте Ядерной Физики, защитил кандидатскую диссертацию в 1991 г. Работы для студентов выполняю уже 30 лет.
    #Кандидатские #Магистерские
    2271 Выполненная работа
    Егор В. кандидат наук, доцент
    5 (428 отзывов)
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Ск... Читать все
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Скорее всего Ваш заказ будет выполнен раньше срока.
    #Кандидатские #Магистерские
    694 Выполненных работы
    Анна С. СФ ПГУ им. М.В. Ломоносова 2004, филологический, преподав...
    4.8 (9 отзывов)
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания... Читать все
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания и проверки (в качестве преподавателя) контрольных и курсовых работ.
    #Кандидатские #Магистерские
    16 Выполненных работ

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

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