Каково имя алгоритма решения, отвечающего «да» или «возможно»?

Question

Мне интересно, что такое имя алгоритма решения, которое делает не возвращает «да» или «нет», но может решить только «да» для реального подмножества входов и не может дать окончательное решение для остальных ,

Подходящим примером будет алгоритм для решения обратимости матрицы - мой алгоритм правильно отвечает «да» для подкласса матриц, но не может ни подтвердить, ни опровергнуть его для остальных.

На мой взгляд, это (своего рода) звук под аппроксимацией реального ответа, но Википедия определяет алгоритм аппроксимации только в областях оптимизации.

Благодарим вас за ввод!

Answer 1

Возможно, речь идет о рандомизированных/вероятностных алгоритмах или рандомизированных структурах данных.

Алгоритмы, которые вероятностно определяют, является ли число простым или нет (a primality test), являются примерами таких рандомизированных алгоритмов. Алгоритм Миллера-Рабина является конкретным примером.

Структуры данных могут быть построены для использования вероятности некоторых операций. A bloom filter - одна такая вероятностная структура данных.

Answer 2

Las-Vegas algorithms что-то очень похоже: если алгоритм Лас-Вегаса завершается, результат верный. Если это не так - это ваш «возможно».

Фактически в реальной жизни эти алгоритмы будут прерваны через некоторое время без результата.