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

Гаевой Никита Сергеевич
Бесплатно
В избранное
Работа доступна по лицензии 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.2 (25 отзывов)
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт напис... Читать все
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт написания магистерских диссертаций. Направление - связь, телекоммуникации, информационная безопасность, информационные технологии, экономика. Пишу научные статьи уровня ВАК и РИНЦ. Работаю техническим директором интернет-провайдера, имею опыт работы ведущим сотрудником отдела информационной безопасности филиала одного из крупнейших банков. Образование - высшее профессиональное (в 2006 году окончил военную Академию связи в г. Санкт-Петербурге), послевузовское профессиональное (в 2018 году окончил аспирантуру Уральского федерального университета). Защитил диссертацию на соискание степени "кандидат технических наук" в 2020 году. В качестве хобби преподаю. Дисциплины - сети ЭВМ и телекоммуникации, информационная безопасность объектов критической информационной инфраструктуры.
    #Кандидатские #Магистерские
    33 Выполненных работы
    Сергей Е. МГУ 2012, физический, выпускник, кандидат наук
    4.9 (5 отзывов)
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым напра... Читать все
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым направлениям физики, математики, химии и других естественных наук.
    #Кандидатские #Магистерские
    5 Выполненных работ
    Екатерина Д.
    4.8 (37 отзывов)
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два об... Читать все
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два образования: экономист-менеджер и маркетолог. Буду рада помочь и Вам.
    #Кандидатские #Магистерские
    55 Выполненных работ
    Дмитрий Л. КНЭУ 2015, Экономики и управления, выпускник
    4.8 (2878 отзывов)
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    #Кандидатские #Магистерские
    5125 Выполненных работ
    Ксения М. Курганский Государственный Университет 2009, Юридический...
    4.8 (105 отзывов)
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитыв... Читать все
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитывать все требования и пожелания.
    #Кандидатские #Магистерские
    213 Выполненных работ
    Яна К. ТюмГУ 2004, ГМУ, выпускник
    5 (8 отзывов)
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соот... Читать все
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соответствии с Вашими требованиями.
    #Кандидатские #Магистерские
    12 Выполненных работ
    Анастасия Л. аспирант
    5 (8 отзывов)
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибост... Читать все
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибостроение, управление качеством
    #Кандидатские #Магистерские
    10 Выполненных работ
    Катерина М. кандидат наук, доцент
    4.9 (522 отзыва)
    Кандидат технических наук. Специализируюсь на выполнении работ по метрологии и стандартизации
    Кандидат технических наук. Специализируюсь на выполнении работ по метрологии и стандартизации
    #Кандидатские #Магистерские
    836 Выполненных работ
    Александр Р. ВоГТУ 2003, Экономический, преподаватель, кандидат наук
    4.5 (80 отзывов)
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфин... Читать все
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфинансы (Казначейство). Работаю в финансовой сфере более 10 лет. Банки,риски
    #Кандидатские #Магистерские
    123 Выполненных работы

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

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