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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .