Collapse of PP with a semi-random source to BPP
From MaRDI portal
Publication:286973
DOI10.1016/S0020-0190(96)00201-3zbMath1336.68091MaRDI QIDQ286973
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
computational complexity; combinatorial problems; probabilistic Turing machines; semi-random sources
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)