Как называется класс такого вероятностного алгоритма?

[Bars]

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

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

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

Примеры:

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

Спасибо!

[patzer2097]

Bars в сообщении #948471 писал(а):

время их работы не полиномиально в худжем случае, но полиномиально с вероятносью p

Понимаете, когда Вы говорите о вероятности, следует указать, к чему эта вероятность относится. Что у Вас случайно - или алгоритм имеет доступ к генератору случайных чисел, или вход для алгоритма выбирается случайно, или еще что-то? И примеры не слишком удачны, ведь quicksort полиномиален в худшем случае.

[venco]

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

[patzer2097]

venco в сообщении #948489 писал(а):

Это же как раз определение NP.

Я бы так не сказал. Но принципиальное отличие $\operatorname{NP}$ от того, о чем пишет ТС, в том, что ТС пишет о какой-то вероятности. Будем надеяться, он уточнит, вероятность чего он имеет в виду.

[Sender]

Существует понятие алгоритма, полиномиального в среднем. Например, вот.

[Bars]

Спасибо за ваши ответы и прошу извенить за мой поздний ответ, в следующий раз буду отвечать оперативнее

patzer2097 в сообщении #948484 писал(а):

quicksort полиномиален в худшем случае.

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

[patzer2097]

Bars в сообщении #963746 писал(а):

а алгоритм выродится в сортировку пузырьком

которая тоже полиномиальна
вообще нужно сильно постараться, чтобы придумать неполиномиальный алгоритм сортировки

[Bars]

Согласен. Quicksoft тут не при чем