reductions from $SAT$ to $DSAT$ and $DSAT$ to $SAT$

Question

can someone help me to prove or disprove the 3 claims about reductionsbetween $SAT$ and $DSAT$, where:

$SAT=\{<\phi> | \text{$\phi$ is bolean formula in $CNF$ and there is an interpretation that satisfies $\phi$}\}$

$DSAT=\{<\phi> | \text{$\phi$ is bolean formula in $DNF$ and there is an interpretation that satisfies $\phi$}\}$

The 3 claimes:

1. There is polynomial reduction from $SAT$ to $DSAT$.
2. There is polynomial reduction from $DSAT$ to $SAT$.
3. There is Logarithmic reduction from $SAT$ to $DSAT$.

I am very confused... I think that there is a distinction on the running time between converting CNF to DNF and converting DNF to CNF but I don't know why and how to figure it out.

Any help will be appreciated

Answer 1

A Boolean function in DNF tells you explicitly which configurations satisfy it. This is feasible to determine in polynomial time. We iterate through the products to determine if one does not contain both a variable and its negation. If one such product is found, configure the variables so that product is $1$. Then the Boolean function is satisfiable. This is linear in the number of products and quadratic in the number of clauses.

SAT is NP-Complete, while DSAT is in P. We don't know if a polynomial time reduction exists from SAT to DSAT, as that would imply P = NP. A logspace computation necessarily takes polynomial time.

As P is a subset of NP and SAT is NP-Complete, there exists a polynomial time reduction from DSAT to SAT.