Premiile Ad Astra
Revista Ad Astra
Biblioteca de știință
Cartea albă
Topul universităților
Who's who
Publicații
Teze și dizertații
Asociația Ad Astra
 
Comunicate
Știri
Evenimente
Oportunități de finanțare
 
Login
Înregistrare
 
>> English
 
   
 

Gabriel Istrate, Adrian Craciun. Proof complexity and the Lovasz-Kneser Theorem. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT' 14), vol. 8561 , pp. 138-153. Lecture Notes in Computer Science, Springer Verlag, 2014.

Rezumat: We investigate the proof complexity of a class of propositional formulas expressing a combinatorial principle known as the Kneser-Lovasz Theorem. This is a family of propositional tautologies, indexed by an nonnegative integer parameter k that generalizes the Pigeonhole Principle (PHP, obtained for k=1).

We show, for all fixed k, 2^{Omega(n)} lower bounds on resolution complexity and exponential lower bounds for bounded depth Frege proofs. These results hold even for the more restricted class of formulas encoding Schrijver's strengthening of the Kneser-Lovasz Theorem. On the other hand for the cases k=2,3 (for which combinatorial proofs of the Kneser-Lovasz Theorem are known) we give polynomial size Frege (k=2), respectively extended Frege (k=3) proofs. The paper concludes with a brief discussion of the results (that will be presented in a subsequent paper) on the complexity of the general case of the Kneser-Lovasz theorem.

A free preliminary version is available at http://arxiv.org/abs/1402.4338

Cuvinte cheie: combinatorial topology, resolution complexity, Frege proofs

URL: http://link.springer.com/chapter/10.1007/978-3-319-09284-3_11

Adăugată pe site de Gabriel Istrate

Înapoi

   
© Ad Astra 2001-2013