Simple but hard mixed horn formulas

Gayathri Namasivayam; Mirosław Truszczyński

doi:10.1007/978-3-642-14186-7_36

Simple but hard mixed horn formulas

Gayathri Namasivayam, Mirosław Truszczyński

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

We study simple classes of mixed Horn formulas, in which the structure of the Horn part is drastically constrained. We show that the SAT problem for formulas in these classes remains NP-complete, and demonstrate experimentally that formulas randomly generated from these classes are hard for the present SAT solvers, both complete and local-search ones.

Original language	English
Title of host publication	Theory and Applications of Satisfiability Testing - 13th International Conference, SAT 2010, Proceedings
Pages	382-387
Number of pages	6
DOIs	https://doi.org/10.1007/978-3-642-14186-7_36
State	Published - 2010
Event	13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010 - Edinburgh, United Kingdom Duration: Jul 11 2010 → Jul 14 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6175 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010
Country/Territory	United Kingdom
City	Edinburgh
Period	7/11/10 → 7/14/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-14186-7_36

Cite this

Namasivayam, G., & Truszczyński, M. (2010). Simple but hard mixed horn formulas. In Theory and Applications of Satisfiability Testing - 13th International Conference, SAT 2010, Proceedings (pp. 382-387). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6175 LNCS). https://doi.org/10.1007/978-3-642-14186-7_36

@inproceedings{7a8c2c557a3649e8b1be29b3814d0a7c,

title = "Simple but hard mixed horn formulas",

abstract = "We study simple classes of mixed Horn formulas, in which the structure of the Horn part is drastically constrained. We show that the SAT problem for formulas in these classes remains NP-complete, and demonstrate experimentally that formulas randomly generated from these classes are hard for the present SAT solvers, both complete and local-search ones.",

author = "Gayathri Namasivayam and Miros{\l}aw Truszczy{\'n}ski",

note = "Copyright: Copyright 2010 Elsevier B.V., All rights reserved.; 13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010 ; Conference date: 11-07-2010 Through 14-07-2010",

year = "2010",

doi = "10.1007/978-3-642-14186-7_36",

language = "English",

isbn = "3642141854",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "382--387",

booktitle = "Theory and Applications of Satisfiability Testing - 13th International Conference, SAT 2010, Proceedings",

}

Namasivayam, G & Truszczyński, M 2010, Simple but hard mixed horn formulas. in Theory and Applications of Satisfiability Testing - 13th International Conference, SAT 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6175 LNCS, pp. 382-387, 13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010, Edinburgh, United Kingdom, 7/11/10. https://doi.org/10.1007/978-3-642-14186-7_36

Simple but hard mixed horn formulas. / Namasivayam, Gayathri; Truszczyński, Mirosław.
Theory and Applications of Satisfiability Testing - 13th International Conference, SAT 2010, Proceedings. 2010. p. 382-387 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6175 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Simple but hard mixed horn formulas

AU - Namasivayam, Gayathri

AU - Truszczyński, Mirosław

PY - 2010

Y1 - 2010

N2 - We study simple classes of mixed Horn formulas, in which the structure of the Horn part is drastically constrained. We show that the SAT problem for formulas in these classes remains NP-complete, and demonstrate experimentally that formulas randomly generated from these classes are hard for the present SAT solvers, both complete and local-search ones.

AB - We study simple classes of mixed Horn formulas, in which the structure of the Horn part is drastically constrained. We show that the SAT problem for formulas in these classes remains NP-complete, and demonstrate experimentally that formulas randomly generated from these classes are hard for the present SAT solvers, both complete and local-search ones.

UR - http://www.scopus.com/inward/record.url?scp=77955010646&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955010646&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14186-7_36

DO - 10.1007/978-3-642-14186-7_36

M3 - Conference contribution

AN - SCOPUS:77955010646

SN - 3642141854

SN - 9783642141850

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 382

EP - 387

BT - Theory and Applications of Satisfiability Testing - 13th International Conference, SAT 2010, Proceedings

T2 - 13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010

Y2 - 11 July 2010 through 14 July 2010

ER -

Simple but hard mixed horn formulas

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this