A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem

DOI10.1137/S0097539798343891zbMath0963.68230OpenAlexW2025994943MaRDI QIDQ4507365

No author found.

Publication date: 18 October 2000

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

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

zbMATH Keywords

samplingcomputational complexitytheory of computationpseudorandom generatorscomplexity classesresource-bounded measureprobabilistic computationpolynomial reductionsautoreducibilitybetting games

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items

Comparing notions of randomness ⋮ Almost complete sets. ⋮ Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds ⋮ Kolmogorov-Loveland randomness and stochasticity ⋮ Closure of resource-bounded randomness notions under polynomial time permutations

This page was built for publication: A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem