Complexity of problem that can be solved by exponentially many SATs

Question

I have two decision problems (function problems, actually) that are closely linked. The first one consists in finding a variable assignment to $x$ Boolean variables so that a specification $A$ is met.

The whole problem can be reduced to FSAT and vice versa, making it FNP-Complete.

Now there's a second problem related to the first, which is to determine all variable assignments to the $x$ variables, for which $A$ is met.

What is the computational complexity of this problem?

It can be solved by applying SAT $2^x$ (i.e., an exponential number of) times; so that is not a valid reduction.

This is like finding all satisfying assignments to a SAT problem. Strangely I did not find much on this in Papadimitriou's book.

Answer 1

The problem you defined is not in FNP as by definition the length of the answer should be polynomial in the length of its input.

Even if we are guaranteed that the length of "y" (output of the function) is polynomial in length of formula (i.e., there are at most polynomially many answer), this problem is not FNP except P= CoNP.

Proof:

$$\hspace{-1cm} F(\phi)= y \Leftrightarrow \forall A: $$ $$\hspace{5cm} {\huge(} A\models \phi \Rightarrow M(A,y) \land $$ $$\hspace{5cm} A\not\models \phi \Rightarrow \lnot M(A,y){\huge )} $$

Where $M(A,y)$ is a polynomial time computable function returning true iff assignment $A$ is in the set of assignments $y$.

Definition of FNP requires us to have a polynomial time function $P$ given $\phi$ and $y$, returns true iff $F(\phi)=y$. That is, deciding if the following formula is tautology or not should be verifiable in P:

$$\Phi (A)= {\huge(} \left(A\models \phi \Rightarrow M(A,y)\right) \land \left(A\not\models \phi \Rightarrow \lnot M(A,y)\right){\huge )} $$