Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness HUBIE CHEN, Universidad del País Vasco and IKERBASQUE, Basque Foundation for Science We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res that is based on the established proof system QU-resolution. Our main results include an exponential separation of the treelike and general versions of relaxing QU-res and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity. CCS Concepts: ¢ Theory of computation ’ Complexity classes; Proof complexity; Additional Key Words and Phrases: Proof complexity, quantified formulas, polynomial hierarchy ACM Reference format: Hubie Chen. 2017. Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness. ACM Trans. Comput. Theory 9, 3, Article 15 (September 2017), 20 pages. https://doi.org/10.1145/3087534 1 INTRODUCTION Background. Traditionally, the area of propositional proof complexity studies http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

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

Download PDF
20 pages

Loading next page...
 
/lp/association-for-computing-machinery/proof-complexity-modulo-the-polynomial-hierarchy-understanding-TWROHgNjHC
Publisher
Association for Computing Machinery
Copyright
Copyright © 2017 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/3087534
Publisher site
See Article on Publisher Site

Abstract

Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness HUBIE CHEN, Universidad del País Vasco and IKERBASQUE, Basque Foundation for Science We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res that is based on the established proof system QU-resolution. Our main results include an exponential separation of the treelike and general versions of relaxing QU-res and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity. CCS Concepts: ¢ Theory of computation ’ Complexity classes; Proof complexity; Additional Key Words and Phrases: Proof complexity, quantified formulas, polynomial hierarchy ACM Reference format: Hubie Chen. 2017. Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness. ACM Trans. Comput. Theory 9, 3, Article 15 (September 2017), 20 pages. https://doi.org/10.1145/3087534 1 INTRODUCTION Background. Traditionally, the area of propositional proof complexity studies

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Oct 9, 2017

There are no references for this article.