The Separation of Relativized Versions of P and DNP for the Ring of the Reals
Christine Gaßner · Zenodo (CERN European Organization for Nuclear Research) · 2020
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