Lower Bounds and Derandomization

Complexity;Derandomization;Computer Science

Gardezi, Jaffer

University of Waterloo

关键词: Complexity;    Derandomization;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3897/1/thesis15.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

A major open problem in complexity theory is to determine whether randomized complexity classes such as BPP, AM, and MA have any nontrivial derandomization. This thesis investigates the derandomization of two randomized versions of the polynomial hierarchy.