License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.74
URN: urn:nbn:de:0030-drops-186085
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18608/
Go to the corresponding LIPIcs Volume Portal

Papamakarios, Theodoros

A Super-Polynomial Separation Between Resolution and Cut-Free Sequent Calculus

pdf-format:
LIPIcs-MFCS-2023-74.pdf (0.7 MB)

Abstract

We show a quadratic separation between resolution and cut-free sequent calculus width. We use this gap to get, for the first time, first, a super-polynomial separation between resolution and cut-free sequent calculus for refuting CNF formulas, and secondly, a quadratic separation between resolution width and monomial space in polynomial calculus with resolution. Our super-polynomial separation between resolution and cut-free sequent calculus only applies when clauses are seen as disjunctions of unbounded arity; our examples have linear size cut-free sequent calculus proofs writing, in a particular way, their clauses using binary disjunctions. Interestingly, this shows that the complexity of sequent calculus depends on how disjunctions are represented.

BibTeX - Entry

@InProceedings{papamakarios:LIPIcs.MFCS.2023.74,
  author =	{Papamakarios, Theodoros},
  title =	{{A Super-Polynomial Separation Between Resolution and Cut-Free Sequent Calculus}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{74:1--74:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18608},
  URN =		{urn:nbn:de:0030-drops-186085},
  doi =		{10.4230/LIPIcs.MFCS.2023.74},
  annote =	{Keywords: Proof Complexity, Resolution, Cut-free LK}
}

Keywords: Proof Complexity, Resolution, Cut-free LK
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI