Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PROOF COMPLEXITY:
Reports tagged with Proof Complexity:
TR97-048 | 13th October 1997
Soren Riis, Meera Sitharam

Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

The semantics of decision problems are always essentially independent of the
underlying representation. Thus the space of input data (under appropriate
indexing) is closed
under action of the symmetrical group $S_n$ (for a specific data-size)
and the input-output relation is closed under the action of $S_n$.
more >>>


TR98-067 | 12th November 1998
Paul Beame

Propositional Proof Complexity: Past, Present and Future

Proof complexity, the study of the lengths of proofs in
propositional logic, is an area of study that is fundamentally connected
both to major open questions of computational complexity theory and
to practical properties of automated theorem provers. In the last
decade, there have been a number of significant advances ... more >>>


TR99-022 | 14th June 1999
Eli Ben-Sasson, Avi Wigderson

Short Proofs are Narrow - Resolution made Simple

The width of a Resolution proof is defined to be the maximal number of
literals in any clause of the proof. In this paper we relate proof width
to proof length (=size), in both general Resolution, and its tree-like
variant. The following consequences of these relations reveal width as ... more >>>


TR00-005 | 17th January 2000
Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Near-Optimal Separation of Treelike and General Resolution

We present the best known separation
between tree-like and general resolution, improving
on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.
This is done by constructing a natural family of contradictions, of
size $n$, that have $O(n)$-size resolution
refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.
This result ... more >>>


TR00-008 | 20th January 2000
Albert Atserias, Nicola Galesi, Ricard Gavaldà

Monotone Proofs of the Pigeon Hole Principle

We study the complexity of proving the Pigeon Hole
Principle (PHP) in a monotone variant of the Gentzen Calculus, also
known as Geometric Logic. We show that the standard encoding
of the PHP as a monotone sequent admits quasipolynomial-size proofs
in this system. This result is a consequence of ... more >>>


TR01-031 | 5th April 2001
Eli Ben-Sasson, Nicola Galesi

Space Complexity of Random Formulae in Resolution

We study the space complexity of refuting unsatisfiable random $k$-CNFs in
the Resolution proof system. We prove that for any large enough $\Delta$,
with high probability a random $k$-CNF over $n$ variables and $\Delta n$
clauses requires resolution clause space of
$\Omega(n \cdot \Delta^{-\frac{1+\epsilon}{k-2-\epsilon}})$,
for any $0<\epsilon<1/2$. For constant $\Delta$, ... more >>>


TR01-074 | 12th October 2001
Joshua Buresh-Oppenheim, David Mitchell

Linear and Negative Resolution are Weaker than Resolution

Comments: 1

We prove exponential separations between the sizes of
particular refutations in negative, respectively linear, resolution and
general resolution. Only a superpolynomial separation between negative
and general resolution was previously known. Our examples show that there
is no strong relationship between the size and width of refutations in
negative and ... more >>>


TR02-003 | 24th December 2001
Eli Ben-Sasson, Yonatan Bilu

A Gap in Average Proof Complexity

We present the first example of a natural distribution on instances
of an NP-complete problem, with the following properties.
With high probability a random formula from this
distribution (a) is unsatisfiable,
(b) has a short proof that can be found easily, and (c) does not have a short
(general) resolution ... more >>>


TR02-023 | 16th April 2002
Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

We prove a quasi-polynomial lower bound on the size of bounded-depth
Frege proofs of the pigeonhole principle $PHP^{m}_n$ where
$m= (1+1/{\polylog n})n$.
This lower bound qualitatively matches the known quasi-polynomial-size
bounded-depth Frege proofs for these principles.
Our technique, which uses a switching lemma argument like other lower bounds
for ... more >>>


TR03-004 | 24th December 2002
Eli Ben-Sasson, Prahladh Harsha

Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

We present a simple proof of the bounded-depth Frege lower bounds of
Pitassi et. al. and Krajicek et. al. for the pigeonhole
principle. Our method uses the interpretation of proofs as two player
games given by Pudlak and Buss. Our lower bound is conceptually
simpler than previous ones, and relies ... more >>>


TR04-012 | 19th December 2003
Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

The Resolution Complexity of Random Graph $k$-Colorability

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.
For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ... more >>>


TR04-112 | 26th November 2004
Neil Thapen, Nicola Galesi

Resolution and pebbling games

We define a collection of Prover-Delayer games that characterize certain subsystems of resolution. This allows us to give some natural criteria which guarantee lower bounds on the resolution width of a formula, and to extend these results to formulas of unbounded initial width.

We also use games to give upper ... more >>>


TR05-053 | 4th May 2005
Paul Beame, Nathan Segerlind

Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>>


TR05-066 | 4th June 2005
Jakob Nordström

Narrow Proofs May Be Spacious: Separating Space and Width in Resolution

Revisions: 2 , Comments: 1

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>


TR06-001 | 1st January 2006
Ran Raz, Iddo Tzameret

The Strength of Multilinear Proofs

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>


TR06-043 | 22nd March 2006
Eran Ofek, Uriel Feige

Random 3CNF formulas elude the Lovasz theta function

Let $\phi$ be a 3CNF formula with n variables and m clauses. A
simple nonconstructive argument shows that when m is
sufficiently large compared to n, most 3CNF formulas are not
satisfiable. It is an open question whether there is an efficient
refutation algorithm that for most such formulas proves ... more >>>


TR06-133 | 14th October 2006
Alex Hertel, Alasdair Urquhart

The Resolution Width Problem is EXPTIME-Complete

The importance of {\em width} as a resource in resolution theorem proving
has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower
bounds on the size of resolution refutations can be proved in a uniform manner by
demonstrating lower bounds on the width ... more >>>


TR06-140 | 8th November 2006
Paul Beame, Russell Impagliazzo, Nathan Segerlind

Formula Caching in DPLL

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>


TR07-007 | 17th January 2007
Jan Krajicek

An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams

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. In fact, the lower bound
applies to semantic derivations operating with sets defined by OBDDs.
We do not assume ... more >>>


TR07-009 | 8th January 2007
Nathan Segerlind

Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Revisions: 1 , Comments: 1

We demonstrate a family of propositional formulas in conjunctive normal form
so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$
to refute using the tree-like OBDD refutation system of
Atserias, Kolaitis and Vardi
with respect to all variable orderings.
All known symbolic quantifier elimination algorithms for satisfiability
generate ... more >>>


TR07-041 | 20th April 2007
Nicola Galesi, Massimo Lauria

Extending Polynomial Calculus to $k$-DNF Resolution

Revisions: 1

We introduce an algebraic proof system Pcrk, which combines together {\em Polynomial Calculus} (Pc) and {\em $k$-DNF Resolution} (Resk).
This is a natural generalization to Resk of the well-known {\em Polynomial Calculus with Resolution} (Pcr) system which combines together Pc and Resolution.

We study the complexity of proofs in such ... more >>>


TR07-046 | 23rd April 2007
Philipp Hertel

An Exponential Time/Space Speedup For Resolution

Comments: 1

Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and diagnosis problems. The main reason for the success is due to highly optimized algorithms for SAT based on resolution. The most successful of these ... more >>>


TR07-078 | 11th August 2007
Ran Raz, Iddo Tzameret

Resolution over Linear Equations and Multilinear Proofs

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>>


TR07-114 | 28th September 2007
Jakob Nordström

A Simplified Way of Proving Trade-off Results for Resolution

We present a greatly simplified proof of the length-space
trade-off result for resolution in Hertel and Pitassi (2007), and
also prove a couple of other theorems in the same vein. We point
out two important ingredients needed for our proofs to work, and
discuss possible conclusions to be drawn regarding ... more >>>


TR08-003 | 25th December 2007
Troy Lee, Adi Shraibman

Disjointness is hard in the multi-party number-on-the-forehead model

We show that disjointness requires randomized communication
Omega(\frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}})
in the general k-party number-on-the-forehead model of complexity.
The previous best lower bound was Omega(\frac{log n}{k-1}). By
results of Beame, Pitassi, and Segerlind, this implies
2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver
proof systems needed to refute certain unsatisfiable ... more >>>


TR08-011 | 21st November 2007
Kazuo Iwama, Suguru Tamaki

The Complexity of the Hajos Calculus for Planar Graphs

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

more >>>

TR08-026 | 28th February 2008
Jakob Nordström, Johan Håstad

Towards an Optimal Separation of Space and Length in Resolution

Most state-of-the-art satisfiability algorithms today are variants of
the DPLL procedure augmented with clause learning. The main bottleneck
for such algorithms, other than the obvious one of time, is the amount
of memory used. In the field of proof complexity, the resources of
time and memory correspond to the length ... more >>>


TR09-002 | 23rd November 2008
Eli Ben-Sasson, Jakob Nordström

Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... more >>>


TR09-003 | 6th January 2009
Alex Hertel, Alasdair Urquhart

Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete

We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known.

The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>>


TR09-034 | 25th March 2009
Eli Ben-Sasson, Jakob Nordström

Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs

Comments: 1

For current state-of-the-art satisfiability algorithms based on the
DPLL procedure and clause learning, the two main bottlenecks are the
amounts of time and memory used. Understanding time and memory
consumption, and how they are related to one another, is therefore a
question of considerable practical importance. In the field of ... more >>>


TR09-047 | 20th April 2009
Eli Ben-Sasson, Jakob Nordström

A Space Hierarchy for k-DNF Resolution

Comments: 1

The k-DNF resolution proof systems are a family of systems indexed by
the integer k, where the kth member is restricted to operating with
formulas in disjunctive normal form with all terms of bounded arity k
(k-DNF formulas). This family was introduced in [Krajicek 2001] as an
extension of the ... more >>>


TR09-072 | 3rd September 2009
Paul Beame, Trinh Huynh

Hardness Amplification in Proof Complexity

Revisions: 2 , Comments: 2

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>


TR09-087 | 1st October 2009
Olga Tveretina, Carsten Sinz, Hans Zantema

Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential
size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential
size: we prove that the size of one ... more >>>


TR09-100 | 16th October 2009
Jakob Nordström, Alexander Razborov

On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordstr&ouml;m 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>


TR10-045 | 15th March 2010
Jakob Nordström

On the Relative Strength of Pebbling and Resolution

Revisions: 1

The last decade has seen a revival of interest in pebble games in the
context of proof complexity. Pebbling has proven to be a useful tool
for studying resolution-based proof systems when comparing the
strength of different subsystems, showing bounds on proof space, and
establishing size-space trade-offs. The typical approach ... more >>>


TR10-054 | 30th March 2010
Jan Krajicek

On the proof complexity of the Nisan-Wigderson generator based on a hard $NP \cap coNP$ function

Let $g$ be a map defined as the Nisan-Wigderson generator
but based on an $NP \cap coNP$-function $f$. Any string $b$ outside the range of
$g$ determines a propositional tautology $\tau(g)_b$ expressing this
fact. Razborov \cite{Raz03} has conjectured that if $f$ is hard on average for
P/poly then these ... more >>>


TR10-059 | 8th April 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Hardness of Parameterized Resolution

Parameterized Resolution and, moreover, a general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that paper, Dantchev et al. show a complexity gap in tree-like Parameterized Resolution for propositional formulas arising from translations of first-order principles.
We broadly investigate Parameterized Resolution obtaining the following ... more >>>


TR10-068 | 15th April 2010
Shir Ben-Israel, Eli Ben-Sasson, David Karger

Breaking local symmetries can dramatically reduce the length of propositional refutations

This paper shows that the use of ``local symmetry breaking'' can dramatically reduce the length of propositional refutations. For each of the three propositional proof systems known as (i) treelike resolution, (ii) resolution, and (iii) k-DNF resolution, we describe families of unsatisfiable formulas in conjunctive normal form (CNF) that are ... more >>>


TR10-081 | 10th May 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games

In this note we show that the asymmetric Prover-Delayer game developed by Beyersdorff, Galesi, and Lauria (ECCC TR10-059) for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form $2^{\Omega(n\log n)}$ for the pigeonhole ... more >>>


TR10-097 | 16th June 2010
Iddo Tzameret

Algebraic Proofs over Noncommutative Formulas

Revisions: 1

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege--yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analogue of Frege proofs, different from that given in Buss ... more >>>


TR10-125 | 11th August 2010
Eli Ben-Sasson, Jakob Nordström

Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions

For current state-of-the-art satisfiability algorithms based on the DPLL procedure and clause learning, the two main bottlenecks are the amounts of time and memory used. In the field of proof complexity, these resources correspond to the length and space of resolution proofs for formulas in conjunctive normal form (CNF). There ... more >>>


TR10-198 | 13th December 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

Parameterized Bounded-Depth Frege is Not Optimal

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>


TR11-006 | 20th January 2011
Sebastian Müller, Iddo Tzameret

Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas

Revisions: 1

Separating different propositional proof systems---that is, demonstrating that one proof system cannot efficiently simulate another proof system---is one of the main goals of proof complexity. Nevertheless, all known separation results between non-abstract proof systems are for specific families of hard tautologies: for what we know, in the average case all ... more >>>


TR11-149 | 4th November 2011
Paul Beame, Chris Beck, Russell Impagliazzo

Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>


TR11-174 | 30th December 2011
Pavel Hrubes, Iddo Tzameret

Short Proofs for the Determinant Identities

Revisions: 1

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>


TR12-018 | 24th February 2012
Joerg Flum, Moritz Müller

Some definitorial suggestions for parameterized proof complexity

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>

TR12-124 | 29th September 2012
Massimo Lauria

A rank lower bound for cutting planes proofs of Ramsey Theorem

Ramsey Theorem is a cornerstone of combinatorics and logic. In its
simplest formulation it says that there is a function $r$ such that
any simple graph with $r(k,s)$ vertices contains either a clique of
size $k$ or an independent set of size $s$. We study the complexity
of proving upper ... more >>>


TR12-132 | 21st October 2012
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

Space Complexity in Polynomial Calculus

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>


TR13-038 | 13th March 2013
Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

The complexity of proving that a graph is Ramsey

Revisions: 1

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of ... more >>>


TR13-042 | 25th March 2013
Siu Man Chan

Just a Pebble Game

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>


TR13-070 | 4th May 2013
Iddo Tzameret

On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation

Revisions: 1

We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>>


TR13-113 | 19th August 2013
Moritz Müller, Stefan Szeider

Revisiting Space in Proof Complexity: Treewidth and Pathwidth

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>>


TR13-185 | 24th December 2013
Fu Li, Iddo Tzameret

Generating Matrix Identities and Proof Complexity Lower Bounds

Revisions: 3

Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field $\mathbb{F}$ let $A$ be a non-commutative (associative) $\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$ of $d\times d$ matrices over $\mathbb{F}$). We say that a non-commutative ... more >>>


TR14-052 | 14th April 2014
Joshua Grochow, Toniann Pitassi

Circuit complexity, proof complexity, and polynomial identity testing

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>


TR14-081 | 13th June 2014
Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals

From Small Space to Small Width in Resolution

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools ... more >>>


TR15-059 | 10th April 2015
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

Feasible Interpolation for QBF Resolution Calculi

In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or expansion-based solving. This both provides the first general lower bound method for QBF ... more >>>


TR15-078 | 4th May 2015
Mladen Mikša, Jakob Nordström

A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good ... more >>>


TR15-134 | 19th August 2015
Fu Li, Iddo Tzameret, Zhengyu Wang

Characterizing Propositional Proofs as Non-Commutative Formulas

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>


TR15-152 | 16th September 2015
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

Are Short Proofs Narrow? QBF Resolution is not Simple.

The groundbreaking paper `Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>>


TR16-101 | 1st July 2016
Toniann Pitassi, Iddo Tzameret

Algebraic Proof Complexity: Progress, Frontiers and Challenges

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>


TR16-202 | 19th December 2016
Dmitry Sokolov

Dag-like Communication and Its Applications

Revisions: 1

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>


TR16-203 | 21st December 2016
Christoph Berkholz, Jakob Nordström

Supercritical Space-Width Trade-offs for Resolution

We show that there are CNF formulas which can be refuted in resolution
in both small space and small width, but for which any small-width
proof must have space exceeding by far the linear worst-case upper
bound. This significantly strengthens the space-width trade-offs in
[Ben-Sasson '09]}, and provides one more ... more >>>


TR17-037 | 25th February 2017
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

Understanding Cutting Planes for QBFs

We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>>


TR17-044 | 21st February 2017
Olaf Beyersdorff, Luke Hinde, Ján Pich

Reasons for Hardness in QBF Proof Systems

Revisions: 1

We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction.

The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via strategy extraction (Beyersdorff & Pich, LICS'16). Here we ... more >>>


TR17-137 | 11th September 2017
Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde

Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs

As a natural extension of the SAT problem, different proof systems for quantified Boolean formulas (QBF) have been proposed. Many of these extend a propositional system to handle universal quantifiers.

By formalising the construction of the QBF proof system from a propositional proof system, by the addition of the ... more >>>


TR17-144 | 27th September 2017
Moritz Müller, Ján Pich

Feasibly constructive proofs of succinct weak circuit lower bounds

Revisions: 1

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>


TR17-151 | 8th October 2017
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Stabbing Planes

Revisions: 3

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by
branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ... more >>>


TR18-024 | 1st February 2018
Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

The Riis Complexity Gap for QBF Resolution

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least ... more >>>


TR18-025 | 1st February 2018
Olaf Beyersdorff, Judith Clymo

More on Size and Width in QBF Resolution

In their influential paper `Short proofs are narrow -- resolution made simple', Ben-Sasson and Wigderson introduced a crucial tool for proving lower bounds on the lengths of proofs in the resolution calculus. Over a decade later their technique for showing lower bounds on the size of proofs, by examining the ... more >>>


TR18-041 | 26th February 2018
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Reordering Rule Makes OBDD Proof Systems Stronger

Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>>


TR18-117 | 23rd June 2018
Fedor Part, Iddo Tzameret

Resolution with Counting: Lower Bounds over Different Moduli

Revisions: 2

Resolution over linear equations (introduced in [RT08]) emerged recently as an important object of study. This refutation system, denoted Res(lin$_R$), operates with disjunction of linear equations over a ring $R$. On the one hand, the system captures a natural ``minimal'' extension of resolution in which efficient counting can be achieved; ... more >>>


TR18-172 | 11th October 2018
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Building Strategies into QBF Proofs

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>


TR18-178 | 9th October 2018
Leroy Chew

Hardness and Optimality in QBF Proof Systems Modulo NP

Quantified Boolean Formulas (QBFs) extend propositional formulas with Boolean quantifiers. Working with QBF differs from propositional logic in its quantifier handling, but as propositional satisfiability (SAT) is a subproblem of QBF, all SAT hardness in solving and proof complexity transfers to QBF. This makes it difficult to analyse efforts dealing ... more >>>


TR18-184 | 5th November 2018
Iddo Tzameret, Stephen Cook

Uniform, Integral and Feasible Proofs for the Determinant Identities

Revisions: 1

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>


TR19-001 | 5th January 2019
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

On OBDD-based algorithms and proof systems that dynamically change order of variables

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>


TR19-057 | 6th April 2019
Olaf Beyersdorff, Joshua Blinkhorn

Proof Complexity of Symmetry Learning in QBF

For quantified Boolean formulas (QBF), a resolution system with a symmetry rule was recently introduced by Kauers and Seidl (Inf. Process. Lett. 2018). In this system, many formulas hard for QBF resolution admit short proofs.

Kauers and Seidl apply the symmetry rule on symmetries of the original formula. Here we ... more >>>


TR19-097 | 4th July 2019
Jacobo Toran, Florian Wörz

Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

Revisions: 1 , Comments: 1

We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>>


TR19-106 | 12th August 2019
Noah Fleming, Pravesh Kothari, Toniann Pitassi

Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 5

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>


TR20-053 | 16th April 2020
Olaf Beyersdorff, Benjamin Böhm

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution

QBF solvers implementing the QCDCL paradigm are powerful algorithms that
successfully tackle many computationally complex applications. However, our
theoretical understanding of the strength and limitations of these QCDCL
solvers is very limited.

In this paper we suggest to formally model QCDCL solvers as proof systems. We
define different policies that ... more >>>


TR20-067 | 30th April 2020
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

Computational and proof complexity of partial string avoidability

The partial string avoidability problem is stated as follows: given a finite set of strings with possible ``holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>>


TR20-082 | 23rd May 2020
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

MaxSAT Resolution and Subcube Sums

Revisions: 2

We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>>


TR20-184 | 10th December 2020
Dmitry Itsykson, Artur Riazanov

Proof complexity of natural formulas via communication arguments

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>


TR20-188 | 12th December 2020
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood

Hard QBFs for Merge Resolution

Revisions: 1

We prove the first proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantified Boolean formulas (QBF) with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs in MRes consist of resolution steps together ... more >>>


TR21-006 | 18th January 2021
Susanna de Rezende, Jakob Nordström, Marc Vinyals

How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>


TR21-012 | 9th February 2021
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

On the Power and Limitations of Branch and Cut

Revisions: 2

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>


TR21-028 | 27th February 2021
Anastasia Sofronova, Dmitry Sokolov

Branching Programs with Bounded Repetitions and $\mathrm{Flow}$ Formulas

Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. '95 who showed the equivalence between regular Resolution and read-once branching programs ... more >>>


TR21-053 | 13th April 2021
Jan Krajicek

Information in propositional proofs and algorithmic proof search

We study from the proof complexity perspective the (informal) proof search problem:
Is there an optimal way to search for propositional proofs?
We note that 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 ... more >>>


TR21-074 | 3rd June 2021
Theodoros Papamakarios, Alexander Razborov

Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

We identify two new big clusters of proof complexity measures equivalent up to
polynomial and $\log n$ factors. The first cluster contains, among others,
the logarithm of tree-like resolution size, regularized (that is, multiplied
by the logarithm of proof length) clause and monomial space, and clause
space, both ordinary and ... more >>>


TR21-097 | 7th July 2021
Jacobo Toran, Florian Wörz

Number of Variables for Graph Identification and the Resolution of GI Formulas

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>


TR21-104 | 26th June 2021
Sravanthi Chede, Anil Shukla

Does QRAT simulate IR-calc? QRAT simulation algorithm for $\forall$Exp+Res cannot be lifted to IR-calc

We show that the QRAT simulation algorithm of $\forall$Exp+Res from [B. Kiesl and M. Seidl, 2019] cannot be lifted to IR-calc.

more >>>

TR21-109 | 20th July 2021
Sravanthi Chede, Anil Shukla

QRAT Polynomially Simulates Merge Resolution.

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021] ) is a refutational proof system for quantified Boolean formulas (QBF). Each line of MRes consists of clauses with only existential literals, together with information of countermodels stored as merge maps. As a result, MRes has strategy extraction by design. The ... more >>>


TR21-131 | 10th September 2021
Olaf Beyersdorff, Benjamin Böhm

QCDCL with Cube Learning or Pure Literal Elimination - What is best?

Revisions: 1

Quantified conflict-driven clause learning (QCDCL) is one of the main approaches for solving quantified Boolean formulas (QBF). We formalise and investigate several versions of QCDCL that include cube learning and/or pure-literal elimination, and formally compare the resulting solving models via proof complexity techniques. Our results show that almost all of ... more >>>


TR21-135 | 6th September 2021
Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl

Strong (D)QBF Dependency Schemes via Implication-free Resolution Paths

We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new infinite collection of implication-free DQBF dependency schemes that generalise the reflexive resolution path dependency scheme. We establish soundness of all these schemes, implying that they can be ... more >>>


TR21-138 | 23rd September 2021
Rahul Santhanam, Iddo Tzameret

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>


TR21-158 | 12th November 2021
Noah Fleming, Toniann Pitassi, Robert Robere

Extremely Deep Proofs

Revisions: 1

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>


TR22-002 | 11th December 2021
Sravanthi Chede, Anil Shukla

Extending Merge Resolution to a Family of Proof Systems

Revisions: 1

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player within the proofs. Every line of this proof system consists of existential clauses along with countermodels. MRes stores ... more >>>


TR22-036 | 10th March 2022
Agnes Schleitzer, Olaf Beyersdorff

Classes of Hard Formulas for QBF Resolution

Revisions: 1

To date, we know only a few handcrafted quantified Boolean formulas (QBFs) that are hard for central QBF resolution systems such as Q and QU, and only one specific QBF family to separate Q and QU.

Here we provide a general method to construct hard formulas for Q and ... more >>>


TR22-040 | 10th March 2022
Benjamin Böhm, Tomáš Peitl, Olaf Beyersdorff

Should decisions in QCDCL follow prefix order?

Quantified conflict-driven clause learning (QCDCL) is one of the main solving approaches for quantified Boolean formulas (QBF). One of the differences between QCDCL and propositional CDCL is that QCDCL typically follows the prefix order of the QBF for making decisions.
We investigate an alternative model for QCDCL solving where decisions ... more >>>


TR22-055 | 23rd April 2022
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

Simple Hard Instances for Low-Depth Algebraic Proofs

We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically, we show that the subset-sum variant $\sum_{i,j,k,l\in[n]} z_{ijkl}x_ix_jx_kx_l-\beta = 0$, for Boolean variables, does not have polynomial-size IPS refutations where the refutations are multilinear and written as ... more >>>


TR22-080 | 25th May 2022
Meena Mahajan, Gaurav Sood

QBF Merge Resolution is powerful but unnatural

The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for this approach was to overcome the limitations encountered in long-distance Q-Resolution proof system (LD-Q-Res), where the syntactic side-conditions, while prohibiting all unsound resolutions, also end ... more >>>


TR22-141 | 20th October 2022
Sam Buss, Noah Fleming, Russell Impagliazzo

TFNP Characterizations of Proof Systems and Monotone Circuits

Revisions: 2

Connections between proof complexity and circuit complexity have become major tools for obtaining lower bounds in both areas. These connections -- which take the form of interpolation theorems and query-to-communication lifting theorems -- translate efficient proofs into small circuits, and vice versa, allowing tools from one area to be applied ... more >>>


TR22-173 | 3rd December 2022
Paul Beame, Sajin Koroth

On Disperser/Lifting Properties of the Index and Inner-Product Functions

Revisions: 1

Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>>


TR23-010 | 13th February 2023
Per Austrin, Kilian Risse

Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove that $f$ does not have circuits of size $s$ (for any $s > \text{poly}(n)$). ... more >>>


TR23-051 | 18th April 2023
Benjamin Böhm, Olaf Beyersdorff

QCDCL vs QBF Resolution: Further Insights

We continue the investigation on the relations of QCDCL and QBF resolution systems. In particular, we introduce QCDCL versions that tightly characterise QU-Resolution and (a slight variant of) long-distance Q-Resolution. We show that most QCDCL variants - parameterised by different policies for decisions, unit propagations and reductions -- lead to ... more >>>


TR23-053 | 19th April 2023
Leroy Chew

Proof Simulation via Round-based Strategy Extraction for QBF

The proof complexity of Quantified Boolean Formulas (QBF) relates to both QBF solving and OBF certification. One method to p-simulate a QBF proof system is by formalising the soundness of its strategy extraction in propositional logic. In this work we illustrate how to use extended QBF Frege to simulate LD-Q(Drrs)-Res, ... more >>>


TR23-063 | 2nd May 2023
Jacobo Toran, Florian Wörz

Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>


TR23-068 | 10th May 2023
Ben Davis, Robert Robere

Colourful TFNP and Propositional Proofs

Revisions: 1

Recent work has shown that many of the standard TFNP classes — such as PLS, PPADS, PPAD, SOPL, and EOPL — have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem ... more >>>


TR23-159 | 31st October 2023
Guangxu Yang, Jiapeng Zhang

Communication Lower Bounds for Collision Problems via Density Increment Arguments

Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), Göös and Jain (RANDOM 2022) independently proposed the communication version ... more >>>


TR23-187 | 27th November 2023
Klim Efremenko, Michal Garlik, Dmitry Itsykson

Lower bounds for regular resolution over parities

The proof system resolution over parities (Res($\oplus$)) operates with disjunctions of linear equations (linear clauses) over $\mathbb{F}_2$; it extends the resolution proof system by incorporating linear algebra over $\mathbb{F}_2$. Over the years, several exponential lower bounds on the size of tree-like Res($\oplus$) refutations have been established. However, proving a superpolynomial ... more >>>


TR24-010 | 19th January 2024
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

Black-Box PPP is not Turing-Closed

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>


TR24-030 | 22nd February 2024
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann

Proof Complexity of Propositional Model Counting

Recently, the proof system MICE for the model counting problem #SAT was introduced by Fichte, Hecher and Roland (SAT’22). As demonstrated by Fichte et al., the system MICE can be used for proof logging for state-of-the-art #SAT solvers.
We perform a proof-complexity study of MICE. For this we first simplify ... more >>>


TR24-033 | 24th February 2024
Sam Buss, Emre Yolcu

Regular resolution effectively simulates resolution

Regular resolution is a refinement of the resolution proof system requiring that no variable be resolved on more than once along any path in the proof. It is known that there exist sequences of formulas that require exponential-size proofs in regular resolution while admitting polynomial-size proofs in resolution. Thus, with ... more >>>


TR24-038 | 27th February 2024
Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann

Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

We initiate an in-depth proof-complexity analysis of polynomial calculus (Q-PC) for Quantified Boolean Formulas (QBF). In the course of this we establish a tight proof-size characterisation of Q-PC in terms of a suitable circuit model (polynomial decision lists). Using this correspondence we show a size-degree relation for Q-PC, similar in ... more >>>




ISSN 1433-8092 | Imprint