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
Open Access
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.
BSS machines, oracle machines, relativizations, P-NP problem, Halting Problem