patternMinor
What usage is the delta defined in the polynomial hierarchy?
Viewed 0 times
thewhatpolynomialhierarchyusagedeltadefined
Problem
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?
$\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?
Solution
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.
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.
Context
StackExchange Computer Science Q#42875, answer score: 3
Revisions (0)
No revisions yet.