>
Fa   |   Ar   |   En
   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
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved