JUCS - Journal of Universal Computer Science 15(6): 1186-1205, doi: 10.3217/jucs-015-06-1186
Oracles and Relativizations of the P =? NP Question for Several Structures
expand article infoChristine Gaßner‡
‡ Ernst-Moritz-Arndt-Universität Greifswald, Greifswald, Germany

Corresponding author: Christine Gaßner ( gassnerc@uni-greifswald.de )

© Christine Gaßner.
This article is freely available under the J.UCS Open Content License.
Citation: Gaßner C (2009) Oracles and Relativizations of the P =? NP Question for Several Structures. JUCS - Journal of Universal Computer Science 15(6): 1186-1205. https://doi.org/10.3217/jucs-015-06-1186
Open Access
Abstract
We consider the uniform model of computation over any structure with two constants. For several structures, we construct oracles which imply that the relativized versions of P and NP are equal or are not equal. We construct universal oracles which imply the equality of the relativized versions of P and NP and we show that we lose the possibility to define these oracles recursively if we try to compress their elements to tuples of fixed length. Moreover we give new oracles for the BSS model in order to separate the classes P and NP relative to these oracles.
Keywords
BSS machines, oracle machines, relativizations, P-NP problem, Halting Problem