Score:1

Understanding notation of probability of algorithm equal to 1

us flag

I would like to understand what the following notation means:

let $A$ be a polynomial-time algorithm and say $X(a,n)$ is a probability ensemble where $a\in\{0,1\}^*$ and $n\in\mathbb{N}$.

What does the notation $\Pr[A(X(a,n))=1]$ mean?

et flag
there is one closing round bracket missing in $\Pr[A(X(a,n)=1]$
kelalaka avatar
in flag
The algorithm's output is equal to 1. Common notation that exists in all modern books.
Chito Miranda avatar
us flag
Yes, I understand it outputs 1 but what do we mean by outputting 1 here?
cn flag
What exactly are you asking? "It outputs 1." is a relatively straightforward statement. If it's modeled as a Turing machine, it writes "1" to it's output tape. If it's modeled as a circuit it's output wire carries the value "1".
Chito Miranda avatar
us flag
Let's say $A$ is a PPT distinguisher between two probability ensembles. What do we mean by a distinguisher outputting 1 versus it outputs 0?
cn flag
We don't mean anything beyond the obvious: the output of the algorithm is 0 or 1. Whether those values carry any meaning depends on the specific algorithm.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.