Theoretical Computer Science

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.

## Solution

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