Pergunta

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better:

$$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$

Where r is a truly random bit string and A is a polynomial time deterministic machine. I've been having some problems understanding what this expression means conceptually (or intuitively).

So far these are some of my thoughts and I will try to point out my doubts too.

A is just a standard TM so we can image that on l steps, it will yield $2^l$ branches. Each branch has a chance of occurring depending on which r occurs. Therefore, I was wondering if the above probability expression just mean "the fraction of branches that out yes"? Is that basically the same as the chance that A will output yes on the given random bit string? The thing that was confusing me and I was not sure how to deal with it was that, A(r) always outputs the same thing ("yes" or "no") on a given r (say it always accepts or rejects if r = 1010100 or something), it didn't seem to me that it a probabilistic sense, unless we randomly choose r. So I was wondering how the community interpreted this equation and what it mean.

Also, since this is a probability, it seems to me that A(r) is just r.v. that only takes two values (yes or no), right? So this distribution only has two probability values, the one that A outputs yes or no, right? I was wondering how that related to the string r and I was not sure how to resolve this.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top