Вопросы с тегом «randomized-algorithms»

10
Когда BPP с предвзятой монетой соответствует стандартному BPP?

Пусть вероятностная машина Тьюринга имеет доступ к недобросовестной монете, которая выпадает в голову с вероятностью (броски независимы). Определите как класс языков, распознаваемых такой машиной за полиномиальное время. Это стандартное упражнение, чтобы доказать, что:pppBPPpBPPpBPP_p A) Если...

10
Примеры использования смещенных оценок

Смещенные оценки полезны в статистике, потому что они могут оптимизировать среднеквадратическую ошибку больше, чем может справиться объективный оценщик . Мне было интересно, есть ли в теории CS какие-нибудь заметные примеры эффективного использования смещенных оценок. Я понимаю, что этот список...

10
Можно ли заменить истинную случайность (доказуемо) случайностью Колмогорова для RP?

Были ли попытки показать, что колмогоровской случайности было бы достаточно для RP ? Будет ли вероятность, использованная в утверждении «Если правильный ответ ДА, то она (вероятностная машина Тьюринга) возвращает ДА ​​с вероятностью ...» всегда будет правильно определена в этом случае? Или для этой...

10
Каковы некоторые результаты по алгоритмам, которые оценивают полиномы по заданному набору точек?

Кажется, есть много рандомизированных алгоритмов для проверки полиномиальной идентичности, проверяя, равен ли данный полином нулю. Есть ли какие-либо результаты алгоритмов, которые делают своего рода оценку полиномов по определенному набору точек? Это может быть, например, аппроксимация, для какой...

10
Классы случайности и сложности малых схем

Пусть некоторый класс сложности и BP- C быть рандомизированное аналог C определяется как БПП по отношению к P . Более формально мы предоставляем полиномиально много случайных битов и принимаем входные данные, если вероятность принять больше...

10
Найти приблизительное значение argmax, используя только приблизительные максимальные запросы

Рассмотрим следующую проблему. Есть неизвестных значений v 1 , ⋯ , v п ∈ R . Задача состоит в том, чтобы найти самый большой индекс, используя только запросы следующей формы. Запрос задается множеством S ⊆ { 1 , ⋯ , n }, и соответствующий ответ max i ∈ S v i . Цель состоит в том, чтобы использовать...

9
Равномерная дерандомизация классов сложности схем

Позволять СС\mathcal{C} быть классом сложности и BP- CBP-С\textrm{BP-}\mathcal{C} быть рандомизированным аналогом СС\mathcal{C} определяется так же, как BPPBPP\textrm{BPP} определяется в отношении пп\textrm{P}, Более формально мы предоставляем полиномиально много случайных битов и принимаем входные...

9
Алгоритм вычисления расстояния между степенями

Данный взаимный a,ba,ba, bМожете ли вы быстро вычислить minx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Вот x,yx,yx, yцелые числа. Очевидно, принимаяx=y=0x=y=0x = y = 0дает неинтересный ответ; в общем, насколько близки эти силы? Кроме того, как мы можем быстро вычислить...

9
Каков наихудший случай алгоритма рандомизированной инкрементной триангуляции Делоне?

Я знаю, что ожидаемое время выполнения алгоритма рандомизированного инкрементального инкрементального триангуляции Делоне (как указано в « Вычислительной геометрии» ) составляет . Существует упражнение, которое подразумевает, что наихудший вариант выполнения - . Я попытался построить пример, где...