6
$\begingroup$

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.)?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.