FEATURED FIELDS
- Theoretical Computer Science
EDITOR IN CHIEF
S. Feigenbaum
Foundation of Science
VOLUME 8, No. 1, October 13 2018
Journal Academica
on-the-go
download Apple® iBooks for iPad®, iPhone®, and iPodTouch®
VOLUME 8, No. 1, October 13 2018
ISSN 2161-3338 (online)
Elnaserledinellah Mahmoud Elsayed Abdelwahab
#2SAT is in P
pp. 003-088
ABSTRACT
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(M^4) or O(M^6) 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(M^9) or O(M^13) 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..
KEYWORDS: Logic, Duality, Variables, Patterns, Container, kSAT, #2SAT, FBDD, P=NP
“The P vs. NP Problem – J.Acad. Lecture Series – #2SAT is in P – Lecture 1/2
45min. lecture on #2SAT is in P
Click here to follow up with Comments, Questions or a Contact Request to the Author!