2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Как называется класс такого вероятностного алгоритма?
Сообщение17.12.2014, 20:57 
Как называется класс сложности алгоритмов, которые дают точный ответ, а но время их работы не полиномиально в худжем случае, но полиномиально с вероятносью p?

Я понимаю, что они относится к NP но этого мало.
Должен же быть какой-то класс, отражающий именну "вероятностно-трудоёмкостную" особенность.
BPP - понятно, не подходит.

Я просто хотел бы завтра на защите немножко сумничать :-)

Примеры:
  • quick sort
  • Поиск неприводимого многочлена в $Z_n$:
    Выбираем случайный h(x)
    Если оказался приводим, то идем на шаг 1.
    Согласен, здесь ответ не "да"/"нет", но этот шаг может быть частью другого алгоритма.
    И тогда для последнего встаёт тот же самый вопрос о его классе.

Спасибо!

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение17.12.2014, 21:15 
Bars в сообщении #948471 писал(а):
время их работы не полиномиально в худжем случае, но полиномиально с вероятносью p
:twisted:
Понимаете, когда Вы говорите о вероятности, следует указать, к чему эта вероятность относится. Что у Вас случайно - или алгоритм имеет доступ к генератору случайных чисел, или вход для алгоритма выбирается случайно, или еще что-то? И примеры не слишком удачны, ведь quicksort полиномиален в худшем случае.

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение17.12.2014, 21:23 
Если я правильно понял идею из примера, то это как раз NP. Проверить кандидат можно за полиномиальное время, но всего кандидатов неполиномиальное количество. Если перебирать все - время не полиномиальное, но если угадать правильный ответ - полиномиальное. Это же как раз определение NP.

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение17.12.2014, 21:39 
venco в сообщении #948489 писал(а):
Это же как раз определение NP.
:twisted:
Я бы так не сказал. Но принципиальное отличие $\operatorname{NP}$ от того, о чем пишет ТС, в том, что ТС пишет о какой-то вероятности. Будем надеяться, он уточнит, вероятность чего он имеет в виду.

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение18.12.2014, 08:23 
Существует понятие алгоритма, полиномиального в среднем. Например, вот.

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение17.01.2015, 21:24 
Спасибо за ваши ответы и прошу извенить за мой поздний ответ, в следующий раз буду отвечать оперативнее

patzer2097 в сообщении #948484 писал(а):
quicksort полиномиален в худшем случае.

В том quicksort, который имею в виду я, есть шаг выбора "медианы", на котором используется генератор случайных чисел. И если на каждом из таких шагов нам не повезёт и в качестве "медианы" нам будут попадатся, скажем, минимальные элементы, то не будет эффекта "разделяй и властвуй", а алгоритм выродится в сортировку пузырьком

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение17.01.2015, 21:46 
Bars в сообщении #963746 писал(а):
а алгоритм выродится в сортировку пузырьком
:twisted: которая тоже полиномиальна
вообще нужно сильно постараться, чтобы придумать неполиномиальный алгоритм сортировки

 
 
 
 Re: Как называется класс такого вероятностного алгоритма?
Сообщение17.01.2015, 22:00 
Согласен. Quicksoft тут не при чем :D

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group