Hard Sets and Pseudo-random Generators for Constant Depth Circuits

摘要

It is shown that the existence of a set in E that is hard for constant depth circuits of subexponential size is equivalent to the existence of a true pseudo-random generator against constant depth circuits.