<p>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.</p>

<p>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.</p>

<p>Proof:</p>

<p>$$\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 )} $$</p>

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

<p>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:</p>

<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 )} $$</p>

CC BY-SA 3.0
2011-07-09T18:54:25.873Z
2011-07-09T18:54:25.873Z
Amir
<p>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.  </p>

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

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

<p>What is the computational complexity of this problem?</p>

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

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

CC BY-SA 3.0
2011-07-09T15:53:42.830Z
http://en.wikipedia.org/wiki/Sharp_P
Huck Bennett
CC BY-SA 3.0
2011-07-09T18:26:12.213Z
“decision problems (function problems, actually)”  Which?
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes><sat>
Complexity of problem that can be solved by exponentially many SATs
Fred
# Complexity of problem that can be solved by exponentially many SATs

(Asked by: username_0 on 2011-07-09)

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.

**Tags:** cc.complexity-theory, complexity-classes, sat

> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Sharp_P  
> **username_2**: “decision problems (function problems, actually)”  Which?  

---

## 1 answers

### Answer by username_3 on 2011-07-09. Score: 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 )} $$


---

