On \(\Delta ^ P_ 2\)-immunity (Q1087016)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On \(\Delta ^ P_ 2\)-immunity |
scientific article; zbMATH DE number 3986642
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On \(\Delta ^ P_ 2\)-immunity |
scientific article; zbMATH DE number 3986642 |
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
0.85537374
0 references
0 references
0.8237126
0 references
0.8111148
0 references
0.8000846
0 references
0 references
0 references
0 references
