Jack Lutz defined a notion of resource-bounded measure to find the relative size of complexity classes within exponential time. He has many surveys and research papers available on this interesting topic. Whether NP has measure zero in EXP is the most exciting open question in this area.
Dieter van Melkebeek noted that the Impagliazzo-Wigderson derandomization results implied a zero-one law for BPP: Either BPP=EXP and has measure one or there is sufficient derandomization to show BPP has measure zero.
The ideas do not directly work for the one-sided error class RP. The new Impagliazzo-Moser paper shows how to overcome these difficulties to get the zero-one law for RP. They also show that if RP does not have measure zero then not only RP but ZPP is equal to EXP. They also show some new derandomization if NP does not have measure zero, i.e., to get that AM = NP.
No comments:
Post a Comment