On Relativizations of the P =? NP Question for Several Structures
Christine Gaßner · Electronic Notes in Theoretical Computer Science · 2008
We consider the uniform model of computation over arbitrary structures with two constants. For several structures, including structures over the reals, we construct oracles which imply that the relativized versions of P and NP are equal or are not equal. Moreover we discuss some special features of these oracles resulting from the undecidability of halting problems in order to explain the difficulties to define structures of finite signature which satisfy P = NP. We show that there are oracles which lose their non-deterministic self-reducibility which is sufficient for a recursive definition if their elements are compressed to tuples of fixed length.