Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

DOI10.4230/LIPIcs.ICALP.2016.94zbMath1387.03067arXiv1410.5369OpenAlexW2757756903MaRDI QIDQ4598235

Hubie Chen

Publication date: 19 December 2017

Full work available at URL: https://arxiv.org/abs/1410.5369

zbMATH Keywords

polynomial hierarchyproof complexityquantified propositional logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (7)

Unnamed Item ⋮ A game characterisation of tree-like Q-resolution size ⋮ Towards Uniform Certification in QBF ⋮ Understanding cutting planes for QBFs ⋮ On Q-Resolution and CDCL QBF Solving ⋮ Unnamed Item ⋮ Hardness and optimality in QBF proof systems modulo NP

This page was built for publication: Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness