# Polynomial time reductions between two problems

I have two sets $A$ and $B$, I want to reduce $A$ to $B$ and $B$ to $A$.

Formulas consist of a finite set of variables $\mathcal{V}$. An assignment $\sigma$ assigns truth values to each variable in $F$. When writing $F(\sigma)$ for an assignment $\sigma : \mathcal{V} \rightarrow \{0, 1\}$ I refer to the application of the assignment to formula $F$ (truth values are assigned to variables in $F$ according to $\sigma$).

Set A contains all unsatisfiable propositional formulas $F$:

$A := \{F \in \mathcal{F}\ | \ \forall \sigma: \mathcal{V} \rightarrow \{0,1\}. \sigma(F) = 0 \}$

Set B contains all propositional formulas which evaluate to the same truth value for an assignment $\sigma$ and its opposite $\overline \sigma$ (this condition must hold for all assignments):

$B := \{F \in \mathcal{F}\ | \ \forall \sigma: \mathcal{V} \rightarrow \{0,1\}. \sigma(F) = \overline\sigma(F) \}$

Let $A \subseteq \Sigma ^*$, $B \subseteq \Gamma ^*$ and $f: \Sigma ^* \rightarrow \Gamma ^*$. By reduction I mean finding a total and computable (in polynomial time) function $f$ such that $\forall w \in \Sigma ^*.w \in A \iff f(w) \in B$ which can be abbreviated by $A \leq B$.

How to do the reductions $A \leq B$ and $B \leq A$? After the reductions are done, does that imply that problems $A$ and $B$ are equally difficult?

• @user1502040 With $\Sigma ^*$ I denote all words which can be constructed with symbols from the alphabet $\Sigma$. In the question, $\Sigma ^*$ means all propositional formulas, also $\Sigma^* = \Gamma ^*$ in the above question. Jul 23 '17 at 13:09

## 1 Answer

You can reduce from $B$ to $A$ by setting $f(F) = (F \neq F^{'})$ where $F^{'}$ is $F$ with every variable replaced with its negation. Equally, you can reduce from $A$ to $B$ by setting $f(F) = F$, because every variable assignment, and its negation, will be false.