Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

A combinatorial characterization of resolution width

  • Atserias, Albert
  • Dalmau, Víctor
We provide a characterization of the resolution width introduced in the context of propositional proof complexity in terms of the existential pebble game introduced in the context of finite model theory. The characterization is tight and purely combinatorial. Our first application of this result is a surprising proof that the minimum space of refuting a 3-CNF formula is always bounded from below by the minimum width of refuting it (minus 3). This solves a well-known open problem. The second application is the unification of several width lower bound arguments, and a new width lower bound for the dense linear order principle. Since we also show that this principle has resolution refutations of polynomial size, this provides yet another example showing that the relationship between size and width cannot be made subpolynomial., Supported in part by CICYT TIN2004-04343 and by the European Commission through the RTN COMBSTRU HPRN-CT2002-00278. Research partially supported by the MEC under the program “Ramon y Cajal,” grants TIC 2002-04470-C03 and TIC 2002-04019-C03, the EU PASCAL Network of Excellence, IST-2002-506778, and the MODNET Marie Curie Research Training Network, MRTN-CT-2004-512234.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Majority constraints have bounded pathwidth duality

  • Dalmau, Víctor
  • Krokhin, Andrei
We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL., This work was partially supported by the UK EPSRC grant EP/C54384X/1. Part of this work was done when both authors visited the Isaac Newton Institute for Mathematical Sciences, Cambridge. The financial support provided by the Institute is gratefully acknowledged. The first author is also supported by the MEC under the program “Ramon y Cajal”, grants TIC 2002-04470-C03, TIC 2002-04019-C03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The second author is also supported by the UK EPSRC grant EP/C543831/1.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Retractions onto series-parallel posets

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Larose, Benoit
The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets . We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P , we describe posets admitting a retraction onto P., Financial help of NSERC Canada is gratefully acknowledged. Víctor Dalmau is partially supported by the MEC under the program “Ramon y Cajal”, Grants TIN 2006-15387-C03-03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. Andrei Krokhin is partially supported by the UK EPSRC Grants EP/C543831/1 and EP/C54384X/1. Benoit Larose is partially supported by NSERC, FQRNT, and CRM.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Majority constraints have bounded pathwidth duality

  • Dalmau, Víctor
  • Krokhin, Andrei
We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL., This work was partially supported by the UK EPSRC grant EP/C54384X/1. Part of this work was done when both authors visited the Isaac Newton Institute for Mathematical Sciences, Cambridge. The financial support provided by the Institute is gratefully acknowledged. The first author is also supported by the MEC under the program “Ramon y Cajal”, grants TIC 2002-04470-C03, TIC 2002-04019-C03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The second author is also supported by the UK EPSRC grant EP/C543831/1.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Retractions onto series-parallel posets

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Larose, Benoit
The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets . We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P , we describe posets admitting a retraction onto P., Financial help of NSERC Canada is gratefully acknowledged. Víctor Dalmau is partially supported by the MEC under the program “Ramon y Cajal”, Grants TIN 2006-15387-C03-03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. Andrei Krokhin is partially supported by the UK EPSRC Grants EP/C543831/1 and EP/C54384X/1. Benoit Larose is partially supported by NSERC, FQRNT, and CRM.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A combinatorial characterization of resolution width

  • Atserias, Albert
  • Dalmau, Víctor
We provide a characterization of the resolution width introduced in the context of propositional proof complexity in terms of the existential pebble game introduced in the context of finite model theory. The characterization is tight and purely combinatorial. Our first application of this result is a surprising proof that the minimum space of refuting a 3-CNF formula is always bounded from below by the minimum width of refuting it (minus 3). This solves a well-known open problem. The second application is the unification of several width lower bound arguments, and a new width lower bound for the dense linear order principle. Since we also show that this principle has resolution refutations of polynomial size, this provides yet another example showing that the relationship between size and width cannot be made subpolynomial., Supported in part by CICYT TIN2004-04343 and by the European Commission through the RTN COMBSTRU HPRN-CT2002-00278. Research partially supported by the MEC under the program “Ramon y Cajal,” grants TIC 2002-04470-C03 and TIC 2002-04019-C03, the EU PASCAL Network of Excellence, IST-2002-506778, and the MODNET Marie Curie Research Training Network, MRTN-CT-2004-512234.