|
|
The Separation of Relativized Versions of P and DNP for the Ring of the Reals
|
|
|
|
|
نویسنده
|
Gaßner Christine
|
منبع
|
journal of universal computer science - 2010 - دوره : 16 - شماره : 18 - صفحه:2563 -2568
|
چکیده
|
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.
|
کلیدواژه
|
BSS model ,binary non-determinism ,digital non-determinism ,oracle machine ,relativizations
|
آدرس
|
Ernst-Moritz-Arndt-Universit¨at Greifswald, Germany
|
پست الکترونیکی
|
gassnerc@uni-greifswald.de
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|