首页 | 本学科首页   官方微博 | 高级检索  
     


On sets turing reducible to p-selective sets
Authors:H. J. Burtschick  W. Lindner
Affiliation:1. Fachbereich Informatik, TU - Berlin, Franklinstrasse 28/29, D-10587, Berlin, Germany
2. Abteilung Theoretische Informatik, Universit?t Ulm, Oberer Eselsberg 3, D-89069, Ulm, Germany
Abstract:We consider sets Turing reducible to p-selective sets under various resource bounds and a restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP/poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP cannot be reduced to the p-selective sets under 2 lin time reductions with at mostn k queries for anyfixed k ε N.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号