Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles

DOI10.3233/FI-2016-1358zbMath1432.03117MaRDI QIDQ4976395

Mikhail Slabodkin, Vsevolod Oparin, Dmitry Sokolov, Dmitry Itsykson

Publication date: 28 July 2017

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

widthresolutionexpanderperfect matchingproof complexity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity of proofs (03F20)

Related Items (3)

Unnamed Item ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs

This page was built for publication: Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles