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.
- Are my observations/conclusions wrong? And if so, please correct me.
- 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