uniform vs. non-uniform PPT

Question

I'm trying to understand PPT and in particular what the differences are in uniform and non-uniform PPT's. First, this is how I see it:

A probabilistic polynomial-time (PPT) algorithm $A$ is an algorithm that runs in polynomial time but also has access to some oracle which provides true random bits. So if we input $x$ into $A$, instead of getting an output $y = A(x)$ that is a deterministic value, we get a random variable $Y$ which has a certain probability of being a set of different values.

A non-uniform PPT $A$ is PPT whose description size (i.e., $|A|$) is not constant, but polynomially increasing with its input. I've seen definitions like $A = \{A_1, A_2, \dots\}$ where every $A_i$ is a PPT.

1. Are my observations/conclusions wrong? And if so, please correct me.
2. Some definitions I have seen for a non-uniform PPT is that we insert some "advice string" along with the input to $A$. But what exactly is that advice string?

Best regards

Answer 1

Your observations are basically correct. Informally it is as follows: For a uniform PPT algorithm think of a fixed Turing machine that has access to some random tape and the output of the algorithm is a random variable. For non-uniform algorithms it is best to think of a family of circuits indexed by the length of the input (so for every input length the algorithm may exhibit a totally different behavior). But you may also see a non-uniform algorithm as a uniform algorithm that takes an additional input-length dependent "advice string" that helps the algorithm to solve problems of that size (to make a non-uniform algorithm uniform, simply pass always the empty string).

For formal definitions just check your beloved complexity theory book. When it comes to crypto, there has recently been some discussion about these two models (typically reductionists proofs are in the uniform model). You may look at the page of Menezes (non-uniformity) and follow up discussion.