Exploiting Dynamically Propositional Logic Structures in SAT

Details Exploiting Dynamically Propositional Logic Structures in SAT Exploiting Dynamically Propositional Logic Structures in SAT

2011-06-07

arxiv.org/abs/1106.1370v1

Computer Science

Logic in Computer Science

6 pages

Scientific paper

The 32-bit hwb (hwb-n32 for short) problem is from equivalence checking that arises in combining two circuits computing the hidden weighted bit function. Since 2002, it remains still unsolvable in every SAT competition. This paper focuses on solving problems such as hwb-n32. Generally speaking, modern solvers can detect only XOR, AND, OR and ITE gates. Other non-clausal formulas (propositional logic structures) cannot be detected. To solve the hwb-n32 problem, we extract dynamically some special propositional logic structures, and then use a variant of DPLL-based solvers to solve the subproblem simplified by the extracted structure information. Using the dynamic extraction technique, we solved efficiently the hwb-n32 problem, even some of which were solved within 3000 seconds.

Affiliated with

Also associated with

No associations

Rating

Exploiting Dynamically Propositional Logic Structures in SAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exploiting Dynamically Propositional Logic Structures in SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploiting Dynamically Propositional Logic Structures in SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26800