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?

  • $\begingroup$ @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. $\endgroup$ – Anna Vopureta Jul 23 '17 at 13:09

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.