On \(\Delta ^ P_ 2\)-immunity (Q1087016)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On \(\Delta ^ P_ 2\)-immunity |
scientific article |
Statements
On \(\Delta ^ P_ 2\)-immunity (English)
0 references
1986
0 references
Immunity properties in the second level of the polynomial-time hierarchy are considered. An argument of Heller is reformulated and strengthened in order to construct a recursive oracle for which \(\Delta^ P_ 2\)-immune sets exist in \(\Sigma^ P_ 2\).
0 references
relativization
0 references
complexity classes
0 references
polynomial-time hierarchy
0 references
recursive oracle
0 references
immune sets
0 references
