Show simple item record

dc.contributor.authorAnsótegui Gil, Carlos José
dc.contributor.authorBéjar Torres, Ramón
dc.contributor.authorFernàndez Camon, César
dc.contributor.authorMateu Piñol, Carles
dc.date.accessioned2013-09-18T15:58:58Z
dc.date.available2013-09-18T15:58:58Z
dc.date.issued2008
dc.identifier.isbn9781577353683
dc.identifier.urihttp://hdl.handle.net/10459.1/46644
dc.description.abstractIn this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and high expansion implies high resolution width. We have extended this approach to generate hard n-ary CSP instances and we have also adapted this idea to increase the expansion of the system of linear equations used to generate XORSAT instances, being able to produce harder satisfiable instances than former generators.ca_ES
dc.language.isoengca_ES
dc.publisherAssociation for the Advancement of Artificial Intelligenceca_ES
dc.relation.isformatofVersió postprint del document publicat a: http://www.aaai.orgca_ES
dc.relation.ispartofProceedings of the twenty-third National Conference on Artificial Intelligence, 2008, p. 1442-1443ca_ES
dc.rights(c) Association for the Advancement of Artificial Intelligence, 2008ca_ES
dc.subject.otherIntel·ligència artificialca_ES
dc.subject.otherTecnologia Innovacionsca_ES
dc.titleGenerating hard SAT/CSP instances using expander graphsca_ES
dc.typearticleca_ES
dc.identifier.idgrec012801
dc.type.versionacceptedVersionca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record