Complexity of representing all satisfying assignments

32 Views Asked by At

I am not formally educated in Complexity Theory hence asking this question. In which complexity class should the problem of representing all satisfying assignments of a Boolean system (equivalently a Boolean formula) belong? This is not a decision problem because we want to know all satisfying assignments. Also this not a counting problem because the set of all satisfying assignments can be far bigger than the set of partial assignments (such as those defined by implicants of the formula) which represents all satisfying assignments.