I\'m trying to understand PPT and in particular what the differences are in unif
ID: 647469 • Letter: I
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 algorithm A is an algorithm that runs in polynomial time but also have 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 which description size, i.e. |A| is not constant, but polynomially increasing with its input. I've seen definitions like A={A1,A2,...} where every Ai is a PPT.
1) Are my observations/conclusions wrong, in if so, please correct me.
2) Some definitions I have seen for a non-uniform PPT is that we insert some "advice string" with the input to A. But what exactly is that advice string?
Best regards
Explanation / Answer
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.