Oracles and Relativizations of the P =? NP Question for Several Structures

Christine Gaßner (Ernst-Moritz-Arndt-Universität Greifswald, Germany)

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

Categories: F.1, F.1.1, F.1.2, F.1.3