The Relationship Between AND/OR Search Spaces and Variable Elimination

In this paper we compare search and inference in graphi-cal models through the new framework of AND/OR search spaces, recently introduced [12]. Specifically, we com-pare Variable Elimination (VE) against memory-intensive AND/OR Search (AO), and will place algorithms suchas graph-based backjumping, no-good learning and lookahead schemes [9], as well as Recursive Conditionin