11

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.

Community
  • 1
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152

1 Answers1

17

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

Luca Trevisan
  • 4,912
  • 28
  • 34