1
$\begingroup$

I have the decision problem $\operatorname{VALID}$ which is the set of all valid propositional formulas (tautologies), I know that $$\overline{\operatorname{SAT}}\equiv_m^p \operatorname{VALID}.$$ This can easily be seen by changing instances of each problem into their logical negation, then a formula is a tautology iff its negation is not satisfiable.

My question is now, for which level of the polynomial time hierarchy PH is $\operatorname{VALID}$ complete. Here a quick definition of PH

$$ \Sigma_0 = \Pi_0=\operatorname{P},\quad \Sigma_{n+1} = \operatorname{NP}(\Sigma_n),\quad \Pi_{n+1} = \operatorname{co}-\Sigma_{n+1},\quad \Delta_{n+1} = \operatorname{P}(\Sigma_{n}).$$

I made the following observations: $\overline{\operatorname{SAT}}\in \operatorname{co}-\operatorname{NP}$, so that by the reduction given earlier we have that $\operatorname{VALID} \in \operatorname{P}(\operatorname{co}-\operatorname{NP})= \operatorname{P}(\operatorname{NP}) = \Delta_2$. So my quess would be that the first level of PH for which $\operatorname{VALID}$ is complete is $\Delta_2$.

If $\overline{\operatorname{SAT}}$ is hard for $\operatorname{co}-\operatorname{NP}$ then I think the result follows, but I cannot seem to corroborate this with solid arguments.

Also, the reduction given seems so simple ($\phi \mapsto \lnot \phi$) that it seems that the class $\operatorname{P}(\operatorname{co}-\operatorname{NP})$ might be a bit overkill.

I would be grateful for any shared insights into this problem.

$\endgroup$

1 Answer 1

1
$\begingroup$

Just like SAT is NP-complete, $\overline{SAT}$ is coNP-complete. More generally, if $L$ is $\Sigma_k$-complete then $\overline{L}$ is $\Pi_k$-complete (and vice versa). You can prove this using the definitions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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