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

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

    user1250010 Омский государственный университет, 2010, преподаватель,...
    4 (15 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    21 Выполненная работа
    Рима С.
    5 (18 отзывов)
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный универси... Читать все
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный университет, являюсь бакалавром, магистром юриспруденции (с отличием)
    #Кандидатские #Магистерские
    38 Выполненных работ
    Сергей Н.
    4.8 (40 отзывов)
    Практический стаж работы в финансово - банковской сфере составил более 30 лет. За последние 13 лет, мной написано 7 диссертаций и более 450 дипломных работ и научных с... Читать все
    Практический стаж работы в финансово - банковской сфере составил более 30 лет. За последние 13 лет, мной написано 7 диссертаций и более 450 дипломных работ и научных статей в области экономики.
    #Кандидатские #Магистерские
    56 Выполненных работ
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Ольга Р. доктор, профессор
    4.2 (13 отзывов)
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласован... Читать все
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласованные сроки и при необходимости дорабатываются по рекомендациям научного руководителя (преподавателя). Буду рада плодотворному и взаимовыгодному сотрудничеству!!! К каждой работе подхожу индивидуально! Всегда готова по любому вопросу договориться с заказчиком! Все работы проверяю на антиплагиат.ру по умолчанию, если в заказе не стоит иное и если это заранее не обговорено!!!
    #Кандидатские #Магистерские
    21 Выполненная работа
    Татьяна Б.
    4.6 (92 отзыва)
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские ди... Читать все
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские диссертации, курсовые работы средний балл - 4,5). Всегда на связи!
    #Кандидатские #Магистерские
    138 Выполненных работ
    Алёна В. ВГПУ 2013, исторический, преподаватель
    4.2 (5 отзывов)
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическо... Читать все
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическое образование. В данный момент работаю преподавателем.
    #Кандидатские #Магистерские
    25 Выполненных работ
    Кормчий В.
    4.3 (248 отзывов)
    Специализация: диссертации; дипломные и курсовые работы; научные статьи.
    Специализация: диссертации; дипломные и курсовые работы; научные статьи.
    #Кандидатские #Магистерские
    335 Выполненных работ
    Петр П. кандидат наук
    4.2 (25 отзывов)
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт напис... Читать все
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт написания магистерских диссертаций. Направление - связь, телекоммуникации, информационная безопасность, информационные технологии, экономика. Пишу научные статьи уровня ВАК и РИНЦ. Работаю техническим директором интернет-провайдера, имею опыт работы ведущим сотрудником отдела информационной безопасности филиала одного из крупнейших банков. Образование - высшее профессиональное (в 2006 году окончил военную Академию связи в г. Санкт-Петербурге), послевузовское профессиональное (в 2018 году окончил аспирантуру Уральского федерального университета). Защитил диссертацию на соискание степени "кандидат технических наук" в 2020 году. В качестве хобби преподаю. Дисциплины - сети ЭВМ и телекоммуникации, информационная безопасность объектов критической информационной инфраструктуры.
    #Кандидатские #Магистерские
    33 Выполненных работы

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

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