All reports by Author Wolfgang Merkle:

__
TR02-056
| 19th September 2002
__

Todd Ebert, Wolfgang Merkle, Heribert Vollmer#### On the Autoreducibility of Random Sequences

__
TR99-034
| 30th August 1999
__

Wolfgang Merkle#### The global power of additional queries to p-random oracles.

Todd Ebert, Wolfgang Merkle, Heribert Vollmer

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

Wolfgang Merkle

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 ...
more >>>