We now explore the new polynomial classes of abduction problems that our algorithm allows to exhibit. Throughout the section, denotes the number of variables in .