Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 16 / Issue 18

available in:   PDF (119 kB) PS (270 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-016-18-2563


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