Satisfiability with exponential families


Scheder, Dominik ; Zumstein, Philipp


[img]
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.




Metadata export


Citation


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item