5
$\begingroup$

At the Wikipedia page, the polynomial hierarchy also defines the following:

$\Delta_0^\text{P} = P$, $\Delta_i^\text{P} = \text{P}^{\Sigma_{i-1}^\text{P}}$

However, the only usage of this anywhere else on the page is the following set of inclusions:

$\Pi_i^P \subseteq \Delta_{i+1}^P \subseteq \Pi_{i+1}^P$.

What usage does this $\Delta_i^P$ class have?

$\endgroup$
3
$\begingroup$

The polynomial hierarchy is an analog of the arithmetical hierarchy in recursion theory, which also has $\Sigma,\Pi,\Delta$, and several other hierarchies also have $\Delta$ terms.

The usage is exactly the same as the usage of $\Sigma_i^P$ and $\Pi_i^P$. For a given problem, you try to find its exact location in the polynomial hierarchy. If a problem is in $\Delta_i^P$ then it can't be $\Sigma_{i+1}^P$-hard (unless the polynomial hierarchy collapses), but perhaps it is $\Delta_i^P$-hard. So you might need these classes for some problems.

$\endgroup$
  • $\begingroup$ If I recall correctly, in recursion theory the $\Delta$ is the intersection of the $\Pi$ and $\Sigma$ of the same level? Here this seems not to be the case (or at least it is not known)? $\endgroup$ – Hendrik Jan May 22 '15 at 17:16
  • $\begingroup$ @HendrikJan At least it is contained in the intersection of $\Pi$ and $\Sigma$. I haven't heard before of equality. $\endgroup$ – Ryan May 22 '15 at 17:49
  • $\begingroup$ @HendrikJan That also confused me, but apparently it's conjecture to be different from the intersection. $\endgroup$ – Yuval Filmus May 22 '15 at 21:52
  • 2
    $\begingroup$ @Ryan not that I know of. $\endgroup$ – Luke Mathieson May 24 '15 at 1:45
  • 1
    $\begingroup$ @Ryan and having real trouble finding one! The $P \subset NP \cap coNP$ is obviously well know, but I think most people prefer to deal with the $PH$ using the alternating quantifier definition, in which case they ignore $\Delta$ classes, so it doesn't get talked about a lot. $\endgroup$ – Luke Mathieson May 25 '15 at 1:17

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.