Motivated by the theory of proof complexity generators we consider the following $Σ^p_2$ search problem $\mbox{DD}_P$ determined by a propositional proof system $P$: given a $P$-proof $π$ of a disjunction $\bigvee_i α_i$, no two $α_i$ having an atom in common, find $i$ such that $α_i \in \mbox{TAUT}$. We formulate a hypothesis (ST) that for some strong proof system $P$ the problem $\mbox{DD}_P$ is not solvable in the student-teacher model with a $p$-time student and a constant number of rounds. The hypothesis follows from the existence of hard one-way permutations. We prove, using a model-theoretic assumption, that (ST) implies $NP \neq coNP$. The assumption concerns the existence of extensions of models of a bounded arithmetic theory and it is open at present if it holds.

Abstract Given a sound first-order p-time theory T capable of formalizing syntax of first-order logic we define a p-time function $g_T$ that stretches all inputs by one bit and we use its properties to show that T must be incomplete. We leave it as an open problem whether for some T the range of $g_T$ intersects all infinite ${\mbox {NP}}$ sets (i.e., whether it is a proof complexity generator hard for all proof systems). A propositional version of the construction shows that at least one of the following three statements is true: 1. There is no p-optimal propositional proof system (this is equivalent to the non-existence of a time-optimal propositional proof search algorithm). 2. $E \not \subseteq P/poly$ . 3. There exists function h that stretches all inputs by one bit, is computable in sub-exponential time, and its range $Rng(h)$ intersects all infinite ${\text {NP}}$ sets.

Abstract We study from the proof complexity perspective the (informal) proof search problem (cf. [17, Sections 1.5 and 21.5]): • Is there an optimal way to search for propositional proofs? We note that, as a consequence of Levin’s universal search, for any fixed proof system there exists a time-optimal proof search algorithm. Using classical proof complexity results about reflection principles we prove that a time-optimal proof search algorithm exists without restricting proof systems iff a p-optimal proof system exists. To characterize precisely the time proof search algorithms need for individual formulas we introduce a new proof complexity measure based on algorithmic information concepts. In particular, to a proof system P we attach information-efficiency function $i_P(\tau )$ assigning to a tautology a natural number, and we show that: • $i_P(\tau )$ characterizes time any P-proof search algorithm has to use on $\tau $ , • for a fixed P there is such an information-optimal algorithm (informally: it finds proofs of minimal information content), • a proof system is information-efficiency optimal (its information-efficiency function is minimal up to a multiplicative constant) iff it is p-optimal, • for non-automatizable systems P there are formulas $\tau $ with short proofs but having large information measure $i_P(\tau )$ . We isolate and motivate the problem to establish unconditional super-logarithmic lower bounds for $i_P(\tau )$ where no super-polynomial size lower bounds are known. We also point out connections of the new measure with some topics in proof complexity other than proof search.

We prove, under a computational complexity hypothesis, that it is consistent with the true universal theory of p-time algorithms that a specific p-time function extending bits to bits violates the dual weak pigeonhole principle: Every string equals the value of the function for some . The function is the truth-table function assigning to a circuit the table of the function it computes and the hypothesis is that every language in P has circuits of a fixed polynomial size .

Proving that there are problems in $\mathsf{P}^\mathsf{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere circuit lower bounds is open even for problems in $\mathsf{MAEXP}$. Giving the notorious difficulty of proving lower bounds that hold for all large input lengths, we ask the following question: Can we show that a large set of techniques cannot prove that $\mathsf{NP}$ is easy infinitely often? Motivated by this and related questions about the interaction between mathematical proofs and computations, we investigate circuit complexity from the perspective of logic. Among other results, we prove that for any parameter $k \geq 1$ it is consistent with theory $T$ that computational class ${\mathcal C} \not \subseteq \textit{i.o.}\mathrm{SIZE}(n^k)$, where $(T, \mathcal{C})$ is one of the pairs: $T = \mathsf{T}^1_2$ and ${\mathcal C} = \mathsf{P}^\mathsf{NP}$, $T = \mathsf{S}^1_2$ and ${\mathcal C} = \mathsf{NP}$, $T = \mathsf{PV}$ and ${\mathcal C} = \mathsf{P}$. In other words, these theories cannot establish infinitely often circuit upper bounds for the corresponding problems. This is of interest because the weaker theory $\mathsf{PV}$ already formalizes sophisticated arguments, such as a proof of the PCP Theorem. These consistency statements are unconditional and improve on earlier theorems of [KO17] and [BM18] on the consistency of lower bounds with $\mathsf{PV}$.

Abstract Let L be a first-order language and Φ and Ψ two L-sentences that cannot be satisfied simultaneously in any finite L-structure. Then obviously the following principle ChainL,Φ,Ψ(n, m) holds: For any chain of finite L-structures C1, …, Cm with the universe [n] one of the following conditions must fail: For each fixed L and parameters n, m the principle ChainL,Φ,Ψ(n,m) can be encoded into a propositional DNF formula of size polynomial in n, m. For any language L containing only constants and unary predicates we show that there is a constant CL such that the following holds: If a constant depth Frege system in DeMorgan language proves ChainL,Φ,Ψ(n, cL . n) by a size s proof then the class of finite L-structures with universe [n] satisfying Φ can be separated from the class of those L-structures on [n] satisfying ψ by a depth 3 formula of size 2log(S)O(1) and with bottom fan-in log(S)O(1).

Abstract We prove an exponential lower bound on the size of proofs in the proof system operating with ordered binary decision diagrams introduced by Atserias, Kolaitis and Vardi [2]. In fact, the lower bound applies to semantic derivations operating with sets defined by OBDDs. We do not assume any particular format of proofs or ordering of variables, the hard formulas are in CNF. We utilize (somewhat indirectly) feasible interpolation. We define a proof system combining resolution and the OBDD proof system.

Abstract We prove the following results: (i) PV proves NP ⊆ P/poly iff PV proves coNP ⊆ NP/O(1). (ii) If PV proves NP ⊆ P/poly then PV proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy, (iii) proves NP ⊆ P/poly iff proves coNP ⊆ NP/O(log n). (iv) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP[log n]. (v) If proves NP ⊆ P/poly then proves that the Polynomial Hierarchy collapses to PNP. Motivated by these results we introduce a new concept in proof complexity: proof systems with advice, and we make some initial observations about them.

Abstract We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories and .

Abstract We consider exponentially large finite relational structures (with the universe {0, 1}n) whose basic relations are computed by polynomial size (nO(1)) circuits. We study behaviour of such structures when pulled back by P/poly maps to a bigger or to a smaller universe. In particular, we prove that: 1. If there exists a P/poly map g: {0, 1}n → {0, 1}m, n < m, iterable for a proof system then a tautology (independent of g) expressing that a particular size n set is dominating in a size 2n tournament is hard for the proof system. 2. The search problem WPHP. decoding RSA or finding a collision in a hashing function can be reduced to finding a size m homogeneous subgraph in a size 22m graph. Further we reduce the proof complexity of a concrete tautology (expressing a Ramsey property of a graph) in strong systems to the complexity of implicit proofs of implicit formulas in weak proof systems.

Abstract We define the notion of approximate Euler characteristic of definable sets of a first order structure. We show that a structure admits a non-trivial approximate Euler characteristic if it satisfies weak pigeonhole principle : two disjoint copies of a non-empty definable set A cannot be definably embedded into A, and principle CC of comparing cardinalities: for any two definable sets A, B either A definably embeds in B or vice versa. Also, a structure admitting a non-trivial approximate Euler characteristic must satisfy . Further we show that a structure admits a non-trivial dimension function on definable sets if and only if it satisfies weak pigeonhole principle : for no definable set A with more than one element can A2 definably embed into A.

Abstract This article is a continuation of our search for tautologies that are hard even for strong propositional proof systems like EF. cf. [14, 15]. The particular tautologies we study, the τ-formulas. are obtained from any /poly map g; they express that a string is outside of the range of g, Maps g considered here are particular pseudorandom generators. The ultimate goal is to deduce the hardness of the τ-formulas for at least EF from some general, plausible computational hardness hypothesis. In this paper we introduce the notions of pseudo-surjective and iterable functions (related to free functions of [15]). These two properties imply the hardness of the τ-formulas from the function but unlike the hardness they are preserved under composition and iteration. We link the existence of maps with these two properties to the provability of circuit lower bounds, and we characterize maps g yielding hard τ-formulas in terms of a hitting set type property (all relative to a propositional proof system). We show that a proof system containing EF admits a pseudo-surjective function unless it simulates a proof system WF introduced by Jeřábek [11]. an extension of EF. We propose a concrete map g as a candidate function possibly pseudo-surjective or free for strong proof systems. The map is defined as a Nisan-Wigderson generator based on a random function and on a random sparse matrix. We prove that it is iterable in a particular way in resolution, yielding the output/input ratio n3 −ε (that improves upon a direct construction of Alekhnovich et al. [2]).

Abstract. We describe a general method how to construct from a prepositional proof system P a possibly much stronger proof system iP. The system iP operates with exponentially long P-proofs described “implicitly” by polynomial size circuits. As an example we prove that proof system iEF, implicit EF, corresponds to bounded arithmetic theory and hence, in particular, polynomially simulates the quantified prepositional calculus G and the -consequences of proved with one use of exponentiation. Furthermore, the soundness of iEF is not provable in . An iteration of the construction yields a proof system corresponding to T2 + Exp and, in principle, to much stronger theories.

Abstract We investigate the possibility to characterize (multi)functions that are -definable with smalli(i= 1, 2, 3) in fragments of bounded arithmeticT2in terms of natural search problems defined over polynomial-time structures. We obtain the following results: (1) A reformulation of known characterizations of (multi)functions that are and -definable in the theories and . (2) New characterizations of (multi)functions that are and -definable in the theory . (3) A new non-conservation result: the theory is not -conservative over the theory . To prove that the theory is not -conservative over the theory , we present two examples of a -principle separating the two theories: (a) the weak pigeonhole principle WPHP(a2,f, g) formalizing that no functionfis a bijection betweena2andawith the inverseg, (b) the iteration principle Iter(a, R, f) formalizing that no functionfdefined on a strict partial order ({0,…, a},R) can have increasing iterates.

Abstract We define a first-order extension LK(CP) of the cutting planes proof system CP as the first-order sequent calculus LK whose atomic formulas are CP-inequalities ∑ i a i · x i ≥ b ( x i 's variables, a i 's and b constants). We prove an interpolation theorem for LK(CP) yielding as a corollary a conditional lower bound for LK(CP)-proofs. For a subsystem R(CP) of LK(CP), essentially resolution working with clauses formed by CP-inequalities, we prove a monotone interpolation theorem obtaining thus an unconditional lower bound (depending on the maximum size of coefficients in proofs and on the maximum number of CP-inequalities in clauses). We also give an interpolation theorem for polynomial calculus working with sparse polynomials. The proof relies on a universal interpolation theorem for semantic derivations [16, Theorem 5.1]. LK(CP) can be viewed as a two-sorted first-order theory of Z considered itself as a discretely ordered Z-module. One sort of variables are module elements, another sort are scalars. The quantification is allowed only over the former sort. We shall give a construction of a theory LK(M) for any discretely ordered module M (e.g., LK(Z) extends LK(CP)). The interpolation theorem generalizes to these theories obtained from discretely ordered Z-modules. We shall also discuss a connection to quantifier elimination for such theories. We formulate a communication complexity problem whose (suitable) solution would allow to improve the monotone interpolation theorem and the lower bound for R(CP).

Abstract A proof of the (propositional) Craig interpolation theorem for cut-free sequent calculus yields that a sequent with a cut-free proof (or with a proof with cut-formulas of restricted form; in particular, with only analytic cuts) with k inferences has an interpolant whose circuit-size is at most k . We give a new proof of the interpolation theorem based on a communication complexity approach which allows a similar estimate for a larger class of proofs. We derive from it several corollaries: (1) Feasible interpolation theorems for the following proof systems: (a) resolution (b) a subsystem of LK corresponding to the bounded arithmetic theory ( α ) (c) linear equational calculus (d) cutting planes. (2) New proofs of the exponential lower bounds (for new formulas) (a) for resolution ([15]) (b) for the cutting planes proof system with coefficients written in unary ([4]). (3) An alternative proof of the independence result of [43] concerning the provability of circuit-size lower bounds in the bounded arithmetic theory ( α ). In the other direction we show that a depth 2 subsystem of LK does not admit feasible monotone interpolation theorem (the so called Lyndon theorem), and that a feasible monotone interpolation theorem for the depth 1 subsystem of LK would yield new exponential lower bounds for resolution proofs of the weak pigeonhole principle.

The weak form of the Hilbert's Nullstellensatz says that a system of algebraic equations over a field, Q/sub i/(x~)=0, does not have a solution in the algebraic closure iff 1 is in the ideal generated by the polynomials Q/sub i/(x~). We shall prove a lower bound on the degrees of polynomials P/sub i/(x~) such that /spl Sigma//sub i/ P/sub i/(x~)Q/sub i/(x~)=1. This result has the following application. The modular counting principle states that no finite set whose cardinality is not divisible by q can be partitioned into q-element classes. For each fixed cardinality N, this principle can be expressed as a propositional formula Count/sub q//sup N/. Ajtai (1988) proved recently that, whenever p, q are two different primes, the propositional formulas Count/sub q//sup qn+1/ do not have polynomial size, constant-depth Frege proofs from instances of Count/sub p//sup m/, m/spl ne/0 (mod p). We give a new proof of this theorem based on the lower bound for the Hilbert's Nullstellensatz. Furthermore our technique enables us to extend the independence results for counting principles to composite numbers p and q. This results in an exact characterization of when Count/sub q/ can be proven efficiently from Count/sub p/, for all p and q.>

Abstract LK is a natural modification of Gentzen sequent calculus for propositional logic with connectives ¬ and ∧,∨ (both of bounded arity). Then for every d ≥ 0 and n ≥ 2, there is a set of depth d sequents of total size O(n3+d) which are refutable in LK by depth d + 1 proof of size exp(O(log2n)) but such that every depth d refutation must have the size at least exp(nΩ(1)). The sets express a weaker form of the pigeonhole principle.

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP).We also obtain an ~(log log rz)depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle.Our theorem nearly completes the search for the exact complexity of the PHP, as Sam Buss has constructed polynomial-size, log ndepth Frege proofs for the PHP.The main lemma in our proof can be viewed as a general H&.stad-style Switching Lemma for restrictions that are partial matchings.Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.

Abstract We consider the problem about the length of proofs of the sentences saying that there is no proof of contradiction in S whose length is < n. We show the relation of this problem to some problems about propositional proof systems.