| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427717 | Information Processing Letters | 2009 | 5 Pages |
Abstract
Denote by C the class of oracles relative to which P=NP (collapsing oracles), and by S the class of oracles relative to which P≠NP (separating oracles). We present structural results on C and S. Using a diagonalization argument, we show that neither C nor S is closed under disjoint union, also known as join. We show that this implies that neither C nor S is closed under union, intersection, or symmetric difference. Consequently EL1, the first level of the extended low hierarchy, is not closed under join.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
