Santhanam (2007) proved that MA/1 does not have circuits of size nk. We translate his result to the heuristic setting by proving that there is a constant a such that for any k, there is a language in HeurMA that cannot be solved by circuits of size nk on more than the 1?1na fraction of inputs.In order to get rid of the non-uniform advice, we supply the inputs with the probability hreshold thatwe use to determine the acceptance. This technique was used by Pervyshev (2007) for proving a time hierarchy for heuristic computations.
展开▼
