Satisfiability with exponential families

Preview

PDF
ssat-postprint.pdf - Accepted
Download (162kB)

DOI:	https://doi.org/10.1007/978-3-540-72788-0_17
URL:	https://madoc.bib.uni-mannheim.de/41138
Additional URL:	http://www.di.fc.ul.pt/~jpms/Events/SAT07/slides/s...
URN:	urn:nbn:de:bsz:180-madoc-411381
Document Type:	Conference or workshop publication
Year of publication:	2007
Book title:	Theory and applications of satisfiability testing - SAT 2007 : 10th International Conference, Lisbon, Portugal, May 28 - 31, 2007; proceedings
The title of a journal, publication series:	Lecture Notes in Computer Science
Volume:	4501
Page range:	148-158
Conference title:	SAT 2007 - 10th International Conference on Theory and Applications of Satisfiability Testing
Location of the conference venue:	Lisbon, Portugal
Date of the conference:	May 28-31, 2007
Publisher:	Marques-Silva, João
Place of publication:	Berlin [u.a.]
Publishing house:	Springer
ISBN:	978-3-540-72787-3 , 978-3-540-72788-0
ISSN:	0302-9743 , 1611-3349
Publication language:	English
Institution:	Zentrale Einrichtungen > University Library
Subject:	004 Computer science, internet
Keywords (English):	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.
Additional information:	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.