Skip Navigation

Journal of Logic and Computation 1997 7(4):457-471; doi:10.1093/logcom/7.4.457
© 1997 by Oxford University Press
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by GRANDJEAN, E.
Right arrow Articles by BÜNING, H. K.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Original Articles

SAT-Problems and Reductions with Respect to the Number of Variables

ETIENNE GRANDJEAN and HANS KLEINE BÜNING

GREYC, Universite de Caen 14032 CAEN Cedex, France E-mail: grandjean{at}infounicaen.fr
FB 17—Mathematik/Informatik, Universität Paderborn 33095 Paderborn, Germany E-mail: kbcsl{at}uni-paderborn.de

We consider polynomial time bounded reductions, in particular between k – SAT, SAT and SAT*, in order to obtain the minimal number of variables. As an example we prove that SAT and Unique SAT have, for deterministic algorithms, the same upper bound of the form O( {Pi} c n) for some c > 1, where n is the number of variables of {Pi}. We show that k – Unique SAT is not harder than k – SAT, but not easier than k(r) – SAT (formulas in k – CNF with at most r positive or negative clauses). Finally we present a proof that for each problem in NTlME(n) there is a polynomial reduction to SAT such that the number of variables in f({Pi}) is only O(n) improving Schnorr–Cook's reduction with O(n log n) variables.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.