Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOUNDED TRUTH-TABLE REDUCIBILITY:
Reports tagged with bounded truth-table reducibility:
TR99-034 | 30th August 1999
Wolfgang Merkle

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


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




ISSN 1433-8092 | Imprint