JUCS - Journal of Universal Computer Science 16(18): 2563-2568, doi: 10.3217/jucs-016-18-2563
The Separation of Relativized Versions of P and DNP for the Ring of the Reals
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 (2010) The Separation of Relativized Versions of P and DNP for the Ring of the Reals. JUCS - Journal of Universal Computer Science 16(18): 2563-2568. https://doi.org/10.3217/jucs-016-18-2563
Open Access
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, oracle machine, relativizations, binary non-determinism, digital non-determinism