Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

On the Resource Bounded Measure of P/poly

Johannes Köbler and Wolfgang Lindner

Abstract:
We show that the class of sets having polynomial size circuits, P/poly, has measure 0 at EXP(NP) under each of the following two assumptions.

  • EXP(NP) is not contained in ZPP(NP(NP)) (which holds if the polynomial time hierarchy does not collapse), or
  • NP is not small at EXP.

Copyright 1998 IEEE. Published in the Proceedings of Complexity'98, April 15-18, 1998 in Buffalo, New York. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works, must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane / P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl. 908-562-3966.

Ps-File: On the Resource Bounded Measure of P/poly