Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is hard if there is no efficient algorithm that solves the problem (with high probability) on instances sampled from D.

Holenstein and Kunzler [2]asked the following question: Question: Does $NP\nsubseteq BPP$ imply that there exists a hard problem in $distNP$?

Impagliazzo [3] showed that any proof that gives a positive answer to the above question must use non-relativizing techniques. More precisely, it is shown that there exists an oracle $O$ such that $NP^O\nsubseteq BPP^O$, and there is no hard problem in $distNP^O$.

My question: Does there exists $X\subset NP$ such that there exists an oracle $O$ such that $X^O\nsubseteq BPP^O$, and there is no hard problem in $distX^O$? More specifically, how about if $X$ is a natural NP-complete problem which is can be represented by paddable language (i.e. we can encode arbitrary additional information, without changing the membership of the instance in the language.)?

  • $\begingroup$ The link to the Impagliazzo paper appears to be broken. Any chance you could spell out the reference? $\endgroup$ – cody Feb 17 at 20:04
  • $\begingroup$ @cody Thank you for your feedback. I have updated the link. Thanks. $\endgroup$ – Rupei Xu Feb 18 at 11:13

Your Answer


Browse other questions tagged or ask your own question.