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

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.