On the Applicability of Post's Lattice

Michael Thomas

For decision problems P defined over Boolean circuits from a restricted set of gates, we have that P(B) AC0 many-one reduces to P(B') for all finite sets B and B' of gates such tha…