Satisfiability with exponential families

Scheder, Dominik ; Zumstein, Philipp

ssat-postprint.pdf - Accepted

Download (162kB)

Additional URL:
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

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


+ 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