Полупрофессиональное членство
-
Определение проблемы полупринадлежности
- Проблема определения, какой элемент множества с большей вероятностью принадлежит ему.
- Альтернатива для различения элемента от нечлена, если в множестве есть хотя бы один элемент.
-
Примеры и сложность
- Пример с двоичными рациональными числами, где проблема решается для пары строк.
- Множество S(x) может быть не рекурсивным, несмотря на наличие рекурсивных селекторов.
-
Селекторы и полурекурсивные множества
- Функция f на упорядоченных парах является селектором, если она возвращает один из элементов пары.
- Множество является полурекурсивным, если оно имеет рекурсивный селектор.
- Полуосуществимые множества имеют небольшие схемы и находятся в расширенной низкой иерархии.
-
Рекомендации и литература
- Статья Дерека Денни-Брауна о последних достижениях в области алгоритмов с неполным членством.
- Статья А. Гемаспандры и М. Торенвлита о теории полуосуществимых алгоритмов.
- Статья К. И Ко о применении методов теории дискретной сложности к численным вычислениям.
- Статья в книге Рональда В. Книга о теории сложности, содержащая исследования в этой области.
-
Заглушка статьи
- Статья является заглушкой и предлагает помощь в расширении Википедии.