Получленство

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

Проблема получленства может быть значительно проще, чем проблема членства. Например, рассмотрим набор S ( x ) двоичных строк конечной длины, представляющих двоично-рациональные числа, меньшие, чем некоторое фиксированное действительное число x . Проблема полупринадлежности для пары строк решается путем выбора строки, представляющей меньшее двоичное рациональное число, поскольку, если ровно одна из строк является элементом, она должна быть меньшей, независимо от значения x . Однако язык S ( x ) может даже не быть рекурсивным языком несчетно , поскольку таких x , а рекурсивных языков только счетно.

Функция f на упорядоченных парах ( x , y ) является селектором для множества S, если f ( x , y ) равна либо x , либо y , и если f ( x , y ) находится в S всякий раз, когда хотя бы один из x , y находится S. в Множество является полурекурсивным, если оно имеет рекурсивный селектор, и P-избирательным или полувозможным, если оно полурекурсивно с полиномиальным селектором по времени.

Полуреализуемые наборы имеют небольшие схемы ; они находятся в расширенной низшей иерархии ; и не может быть NP-полным, если P=NP .

Ссылки

Дерек Денни-Браун, «Алгоритмы получленства: некоторые последние достижения», Технический отчет , факультет компьютерных наук Рочестерского университета, 1994 г.
Лейн А. Хемаспаандра, Мицунори Огихара, «Спутник теории сложности», Тексты по теоретической информатике , серия EATCS, Springer, 2002, ISBN 3-540-67419-5 , стр. 294.
Лейн А. Хемаспаандра, Лин Торенвлит, «Теория полувыполнимых алгоритмов», Монографии по теоретической информатике , Springer, 2003, ISBN 3-540-42200-5 , стр. 1
Кер-И Ко, «Применение методов дискретной теории сложности к численным вычислениям» в книге Рональда В. (редактор), «Исследования по теории сложности», Исследовательские заметки по теоретической информатике , Питман, 1986, ISBN 0-470-20293-9 , с. 40
К. Йокуш-младший (1968). «Полурекурсивные множества и положительная сводимость» (PDF) . Пер. амер. Математика. Соц. 137 : 420–436.

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .