Loading article…
数学および理論計算機科学において、集合の準メンバーシップ問題とは、2つの可能な要素のうち、どちらが論理的にその集合に属する可能性が高いかを決定する問題、あるいは、少なくとも一方が集合に含まれる2つの要素が与えられた場合に、その要素が集合に属するか属さないかを区別する問題である。
半メンバーシップ問題はメンバーシップ問題よりもかなり簡単かもしれません。たとえば、ある固定された実数xより小さい二進有理数を表す有限長の二進文字列の集合S ( x ) を考えてみましょう。文字列のペアに対する半メンバーシップ問題は、より小さい二進有理数を表す文字列を選択することで解決できます。なぜなら、文字列のちょうど一方が要素である場合、xの値に関係なく、それはより小さい値でなければならないからです。しかし、言語S ( x ) は再帰言語ではないかもしれません 。なぜなら、そのようなx は非可算個存在するのに対し、再帰言語は可算個しか存在しないからです。
順序対 ( x , y )上の関数fは、f ( x , y ) が x または y のいずれかに等しく、かつ xとyの少なくとも一方が S に含まれる場合にf ( x , y )がSに含まれる場合、集合 S の選択子である。集合は、再帰的な選択子を持つ場合、半再帰的であり、多項式時間の選択子を持つ半再帰的である場合、 P 選択的または半実行可能である。