What's the meaning of verifier is "ppt" ? and why we need verifier is ppt in Interactive Proof?

Question

I have been studying Zero Knowledge Proof. I found the Definition of Interactive Proof says that Verifier is ppt. And I only found in PP (Complexity) Wikipedia says that ppt:

Turing machines that are polynomially-bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial-time machines.[2] This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2.

Still very confusing about the PPT, what's the full name of PPT? we do we need the verifier to be PPT for interactive Proof?

Resource from: Zero Knowledge Proofs CS276: Cryptography, UC Berkeley

Answer 1

PPT is Probabilistic Polynomial Time Algorithm.

A deterministic verifier will always produce the same output/reply for any input.

Let's take an interactive sequence.

Prover sends $p_1$.

Verifier replies with $f(p_1) = v_1$

Prover replies back with $g(v_1) = p_2$

The function $f$ which the verifier uses is deterministic. i.e. for a particular input, it always replies with the same reply.

In a probabilistic verifier, $f$ also has randomisation as input. i.e. $g$ takes 2 inputs $f(v_i, r)$ where $r$ is a random value. Hence $f$ is not deterministic, and the verifier is a probabilistic verifier. And if $f$ runs in polynomial time, the verifier is a Probabilistic Polynomial Time (PPT) verifier.