The Separation of Relativized Versions of P and DNP for the Ring of the Reals

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

Abstract: We consider the uniform BSS model of computation where the machines can perform additions, multiplications, and tests of the form x ≥ 0. The oracle machines can also check whether a tuple of real numbers belongs to a given oracle set or not. We present oracle sets containing positive integers and pairs of numbers, respectively, such that the classes P and DNP relative to these oracles are not equal. The first set is constructed by diagonalization techniques and the second one is derived from the Knapsack Problem.

Keywords: BSS model, binary non-determinism, digital non-determinism, oracle machine, relativizations

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