Closure Properties and Witness Reduction

摘要

Witness reduction has played a crucial role in several recent results in complexity theory. These include Toda′s result that PH ⊆ BP · ⊕P, the "collapsing" of PH into ⊕P with a high probability; Toda and Ogiwara′s results which "collapse" PH into various counting classes with a high probability; and Ogiwara and Hemachandra′s results describing hard functions for various function classes. Ogiwara and Hemachandra′s results establish a connection between functions being hard for #P and functions interacting with the class to effect witness reduction. In fact, we believe that the ability to achieve some form of witness reduction is what makes a function hard for a class of functions. To support our thesis we define new function classes and obtain results analogous to those of Ogiwara and Hemachandra. We also introduce the notion of randomly hard functions and obtain similar results.