<p>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.</p>

<p>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.</p>

<p>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</p>

CC BY-SA 3.0
2011-04-20T22:12:00.370Z
2011-04-20T22:12:00.370Z
Luca Trevisan
<p>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 <a href="https://cstheory.stackexchange.com/q/5087/873">Problems in NP but not in Average-P/poly</a> and <a href="https://cstheory.stackexchange.com/q/4796/873">Beating Nonuniformity by Oracle Access</a>.</p>

<p><strong>Informal statement:</strong> 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?</p>

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

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

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

<p>The word <strong>solved</strong> can be interpreted as the worst-case or average-case (the latter is preferred).</p>

<p>If natural problems cannot be found easily, artificial problems are acceptable as well.</p>

<cc.complexity-theory><cr.crypto-security><np><advice-and-nonuniformity><average-case-complexity>
Non-Uniform vs. Uniform Adversaries
Sadeq Dousti
# Non-Uniform vs. Uniform Adversaries

(Asked by: username_0 on 2011-02-26)

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](https://cstheory.stackexchange.com/q/5087/873) and [Beating Nonuniformity by Oracle Access](https://cstheory.stackexchange.com/q/4796/873).

**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.

**Tags:** cc.complexity-theory, cr.crypto-security, np, advice-and-nonuniformity, average-case-complexity


---

## 1 answers

### Answer by username_1 on 2011-04-20. Score: 17 | Accepted answer

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


---

