Регистрация Войти
Рейтинг:1
Chito Miranda avatar Crypto

Понимание обозначения вероятности алгоритма равной 1

флаг us
Chito Miranda

Я хотел бы понять, что означает следующее обозначение:

позволять $А$ быть алгоритмом с полиномиальным временем и сказать $Х(а,п)$ представляет собой вероятностный ансамбль, где $а\в\{0,1\}^*$ и $n\in\mathbb{N}$.

Что означает обозначение $\Pr[A(X(a,n))=1]$ иметь в виду?

61
0 + 0
флаг et
user93353
в $\Pr[A(X(a,n)=1]$) отсутствует одна закрывающая круглая скобка
1
Ответить
kelalaka avatar
флаг in
kelalaka
Выход алгоритма равен 1. Общепринятое обозначение, существующее во всех современных книгах.
0
Ответить
Chito Miranda avatar
флаг us
Chito Miranda
Да, я понимаю, что он выводит 1, но что мы подразумеваем под выводом 1 здесь?
0
Ответить
флаг cn
Maeher
Что именно вы спрашиваете? «Выдает 1». является относительно простым утверждением. Если он смоделирован как машина Тьюринга, он записывает «1» на свою выходную ленту. Если он смоделирован как цепь, его выходной провод имеет значение «1».
0
Ответить
Chito Miranda avatar
флаг us
Chito Miranda
Допустим, $A$ — это различитель PPT между двумя вероятностными ансамблями. Что мы подразумеваем под различителем, выводящим 1, по сравнению с выводом 0?
0
Ответить
флаг cn
Maeher
Мы не имеем в виду ничего, кроме очевидного: выход алгоритма равен 0 или 1. Имеют ли эти значения какой-либо смысл, зависит от конкретного алгоритма.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.