# Uniform and Non-Uniform PPTs

I stumbled upon the case in which it was necessary to state whether the authors were assuming uniform or non-uniform attackers. For what I know, non uniform PPT are basically a sequence of PPTs, so $$\mathcal{A}=\{\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}_n\}$$, and on input $$x$$ of size $$|x| = \lambda$$, $$\mathcal{A}_\lambda$$ is called. Why is this model "stronger" than the uniform one? Couldn't ad attacker $$\mathcal{A}$$ just embed all the other attackers into its own description and invoke the suitable one? Are there problems we know how to solve in the uniform model but not (if not with weaker guarantees) in the non-uniform model?

Consider a unary enumeration of all Turing machines, e.g. a machine $$M$$ is represented by $$1^{\lambda_M}$$ for some unique integer $$\lambda_M$$. The halting problem is uncomputable, even in this "sparse" representation. But it is non-uniformly computable, as each Turing machine $$M$$ either halts or does not, and we can "hard-code" deciding this into each turing machine $$A_{\lambda_M}$$.
If we could "uniformly generate" the $$A_i$$'s, meaning efficiently generate them from the solely the description of $$i$$, you would be right. In the above example, you can't, as you don't know whether each Turing machine $$M$$ halts.
• @jacobi_matrix the issue is that you can't build a uniform adversary hard-coding the others into its description, as generating an arbitrary $A_i$ may not be efficiently computable (or even computable at all, for example the "Sparse halting problem" non-uniform algorithm given in my answer). Moreover, you can't just "store" them all in the uniform adversary, as the uniform adversary would have too large of a description. Commented Jun 18, 2021 at 19:31