Alternation-Trading Proofs, Linear Programming, and Lower Bounds

Abstract : A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, Mod6-SAT, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs of these lower bounds follow a certain proof-by-contradiction strategy that we call alternation-trading. An important open problem is to determine how powerful such proofs can possibly be. We propose a methodology for studying these proofs that makes them amenable to both formal analysis and automated theorem proving. We prove that the search for better lower bounds can often be turned into a problem of solving a large series of linear programming instances. Implementing a small-scale theorem prover based on this result, we extract new human-readable time lower bounds for several problems. This framework can also be used to prove concrete limitations on the current techniques.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.669-680, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00456011
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 15:25:39
Dernière modification le : jeudi 11 février 2010 - 17:25:37
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:17:05

Fichier

williams.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00456011, version 1

Collections

Citation

Ryan Williams. Alternation-Trading Proofs, Linear Programming, and Lower Bounds. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.669-680, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00456011〉

Partager

Métriques

Consultations de la notice

132

Téléchargements de fichiers

86