On Tally Relativizations of $BP$-Complexity Classes

DOI10.1137/0218031zbMath0678.68046OpenAlexW2039409656MaRDI QIDQ3835025

Osamu Watanabe, Showen Tang

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218031

zbMATH Keywords

algorithmic information theoryKolmogorov complexityprobabilistic complexity classesrandom oracle sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (7)

Polynomial-time reducibilities and ``almost all oracle sets ⋮ Characterizing polynomial complexity classes by reducibilities ⋮ Structural analysis of the complexity of inverse functions ⋮ On independent random oracles ⋮ Circuit size relative to pseudorandom oracles ⋮ Dot operators ⋮ Probabilistic complexity classes and lowness

This page was built for publication: On Tally Relativizations of $BP$-Complexity Classes