Artificial Intelligence


#2sat is in P

Authors: Elnaserledinellah Mahmood Abdelwahab

This paper presents a new view of logical variables which helps solving efficiently the #P complete #2SAT problem. Variables are considered to be more than mere place holders of information, namely: Entities exhibiting repetitive patterns of logical truth values. Using this insight, a canonical order between literals and clauses of an arbitrary 2CNF Clause Set S is shown to be always achievable. It is also shown that resolving clauses respecting this order enables the construction of small Free Binary Decision Diagrams (FBDDs) for S with unique node counts in O(M4) or O(M6) in case a particular shown Lemma is relaxed, where M is number of clauses. Efficiently counting solutions generated in such FBDDs is then proven to be O(M9) or O(M13) by first running the proposed practical Pattern-Algorithm 2SAT-FGPRA and then the counting Algorithm Count2SATSolutions, so that the overall complexity of counting 2SAT solutions is in P. Relaxing the specific Lemma enables a uniform description of kSAT-Pattern-Algorithms in terms of (k-1)SAT- ones opening up yet another way for showing the main result. This second way demonstrates that avoiding certain types of copies of sub-trees in FBDDs constructed for arbitrary 1CNF and 2CNF Clause Sets, while uniformly expressing kSAT Pattern-Algorithms for any k>0, is a sufficient condition for an efficient solution of kSAT as well. Exponential lower bounds known for the construction of deterministic and non-deterministic FBDDs of some Boolean functions are seen to be inapplicable to the methods described here.

Comments: 85 Pages. Journal Academica Vol. 8(1), pp. 3-88, October 13 2018 - Theoretical Computer Science - ISSN 2161-3338 online edition - Copyright © 2018 Journal Academica Foundation - With perpetual, non-exclusive license for

Download: PDF

Submission history

[v1] 2018-11-14 13:21:48

Unique-IP document downloads: 35 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus