Satisfiability with exponential families
Scheder, Dominik
;
Zumstein, Philipp
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. |
Search Authors in
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
|
Show item |
|
|