9
$\begingroup$

This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to Problems in NP but not in Average-P/poly and Beating Nonuniformity by Oracle Access.

Informal statement: When do non-uniform adversaries (i.e. poly-size family of circuits) succeed in breaking a cryptographic scheme, but uniform adversaries (i.e. probabilistic poly-time Turing machines) do not?

Complexity-theoretic statement: This is not exactly the same as the above informal statement, but I'm actually interested in this version:

What natural problems lie in $(\mathsf{NP} \cap \mathsf{P/poly}) - \mathsf{AvgP}$ ?

In other words, what hard-on-average natural $\mathsf{NP}$ problems can be solved by poly-sized family of circuits?

The word solved can be interpreted as the worst-case or average-case (the latter is preferred).

If natural problems cannot be found easily, artificial problems are acceptable as well.

$\endgroup$
14
$\begingroup$

There is hardly any natural problem which is believed to be in P/poly but not in P. The artificial examples can be adapted to answer your question.

Assume $E \neq NE$, then there is a unary language L in NP which is not in P -- unary means that all the strings in the language have the form $1^n$ for some n.

Then define L' to be the set of all strings x such that $1^{length(x)}$ is in L. This is in NP, it is in P/poly, and it is not in average polynomial time

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.