Publication Date

2-9-1993

Technical Report Number

TR92-37

Subjects

Theory of Computation, Mathematics of Computing

Abstract

It is shown that, for every k>0 and every fixed algorithmically random language B, there is a language that is polynomial-time, truth-table reducible in k+1 queries to B but not truth-table reducible in k queries in *any* amount of time to *any* algorithmically random language C. In aprticular, this yields the separation P (RAND) is a proper subset of P (RAND), k-tt (k+1)-tt where RAND is the set of all algorithmically random languages.

Share

COinS