Up to know, the known derandomization methods have been derived assuming average-case hardness conditions. In this paper we insteak present the first worst-case hardness conditions sufficient to obtain P=BPP. Our conditions refer to the worst-case circuit complexity of Boolean operators computable in time expomential in the input size. Such results are achieved by a new method that departs significantly from the usual known methods based on pseudo-random generators. complexity of Boolean operators computable in NC (with respect to their output size) to obtain NC=BPNC.
展开▼
