10.4230/OASIcs.CCA.2009.2266
Gaßner, Christine
Relativizations of the P =? DNP Question for the BSS Model
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
2009
Computer Science
000 Computer science, knowledge, general works
Herbstritt, Marc
2009-11-25
eng
ConferencePaper
application/pdf
1.0
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC-BY-NC-ND)
We consider the uniform BSS model of computation where the machines can perform additions, multiplications, and tests of the form $x\geq 0$. The oracle machines can also check whether a tuple of real numbers belongs to a given oracle set ${\cal O}$ or not. We construct oracles such that the classes P and DNP relative to these oracles are equal or not equal.