Satisfiability with exponential families

Vorschau

PDF
ssat-postprint.pdf - Angenommene Version
Download (162kB)

DOI:	https://doi.org/10.1007/978-3-540-72788-0_17
URL:	https://madoc.bib.uni-mannheim.de/41138
Weitere URL:	http://www.di.fc.ul.pt/~jpms/Events/SAT07/slides/s...
URN:	urn:nbn:de:bsz:180-madoc-411381
Dokumenttyp:	Konferenzveröffentlichung
Erscheinungsjahr:	2007
Buchtitel:	Theory and applications of satisfiability testing - SAT 2007 : 10th International Conference, Lisbon, Portugal, May 28 - 31, 2007; proceedings
Titel einer Zeitschrift oder einer Reihe:	Lecture Notes in Computer Science
Band/Volume:	4501
Seitenbereich:	148-158
Veranstaltungstitel:	SAT 2007 - 10th International Conference on Theory and Applications of Satisfiability Testing
Veranstaltungsort:	Lisbon, Portugal
Veranstaltungsdatum:	May 28-31, 2007
Herausgeber:	Marques-Silva, João
Ort der Veröffentlichung:	Berlin [u.a.]
Verlag:	Springer
ISBN:	978-3-540-72787-3 , 978-3-540-72788-0
ISSN:	0302-9743 , 1611-3349
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Zentrale Einrichtungen > UB Universitätsbibliothek
Fachgebiet:	004 Informatik
Freie Schlagwörter (Englisch):	satisfiability , context-free grammars , VC-dimension , NP-hardness , polynomial circuits
Abstract:	Fix a set S⊆{0,1}∗ of exponential size, e.g. \|S∩{0,1}^n\|∈Ω(α^n),α>1. The S-SAT problem asks whether a propositional formula F over variables v_1, ..., v_n has a satisfying assignment (v_1,…,v_n)∈{0,1}^n∩S. Our interest is in determining the complexity of S-SAT. We prove that S-SAT is NP-complete for all context-free sets S. Furthermore, we show that if S-SAT is in P for some exponential S, then SAT and all problems in NP have polynomial circuits. This strongly indicates that satisfiability with exponential families is a hard problem. However, we also give an example of an exponential set S for which the S-SAT problem is not NP-hard, provided P≠NP.
Zusätzliche Informationen:	The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-72788-0_17

	Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.
	Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.