×

zbMATH — the first resource for mathematics

Low-end uniform hardness versus randomness tradeoffs for AM. (English) Zbl 1194.68120

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI