Proof Complexity Modulo the Polynomial Hierarchy

DOI10.1145/3087534zbMath1427.03063OpenAlexW2964003362MaRDI QIDQ4973892

Hubie Chen

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3087534

zbMATH Keywords

polynomial hierarchyproof complexityquantified formulas

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (5)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Unnamed Item ⋮ Lower bound techniques for QBF expansion ⋮ Characterising tree-like Frege proofs for QBF ⋮ Unnamed Item

This page was built for publication: Proof Complexity Modulo the Polynomial Hierarchy