期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider separations of reducibilities in the context of
resource-bounded measure theory. First, we show a result on
polynomial-time bounded reducibilities: for every p-random set R,
there is a set which is reducible to R with k+1 non-adaptive
queries, but is not reducible to any other p-random set with at
most k non-adaptive queries. This result solves an open problem
stated in a recent survey paper by Lutz and Mayordomo in the
EATCS-Bulletin 68, 1999.
Second, we show that the separation result above can be transferred
from the setting of polynomial time bounds to a setting of
rec-random sets and recursive reducibilities. This yields as a
special case the main result of a paper by Book, Lutz, and Martin
(Information and Computation 120:49-54,1995 and STACS 1994)
who, by using different methods, showed a similar separation
w.r.t. Martin-L\"{o}f-random sets. Moreover, in both settings
we obtain a separation as above of truth-table versus bounded
truth-table reducibility.
关键词：bounded truth-table reducibility, complexity theory, Resource-bounded measure, resource-bounded random sets, separation of reducibilities, truth-table reducibility
