準会員

数学と理論計算機科学において、集合の半帰属問題とは、2 つの要素のうちどちらが論理的にその集合に属する可能性が高いかを決定する問題、あるいは、少なくとも 1 つが集合に含まれる 2 つの要素が与えられた場合に、その集合の要素と非要素を区別する問題です。

半帰属問題は帰属問題よりもかなり簡単かもしれません。たとえば、ある固定された実数xより小さい二項有理数を表す有限長のバイナリ文字列の集合S ( x ) を考えてみましょう。文字列のペアの半帰属問題は、小さい方の二項有理数を表す文字列を取ることで解決されます。これは、文字列の 1 つだけが要素である場合、xの値に関係なく、その文字列が小さい方になるはずだからです。ただし、言語S ( x ) は再帰言語ではない可能性もあります 。なぜなら、そのようなx は無数にあるのに、再帰言語は可算な数しかないからです。

順序付きペア ( x , y )上の関数f が集合Sのセレクターである場合、それはf ( x , y ) がxまたはy のいずれかと等しく、かつxとyの少なくとも 1 つがSにあるときはいつでもf ( x , y ) がSにある場合です。集合が再帰セレクターを持つ場合、その集合は半再帰的であり、多項式時間セレクターを持つ半再帰的である場合、 P 選択的または半実行可能集合です。

半実行可能集合は回路が小さく、拡張された低階層にあり、P=NPでない限りNP 完全ではありません。

• Derek Denny-Brown、「セミメンバーシップ アルゴリズム: 最近の進歩」、技術レポート、ロチェスター大学コンピュータ サイエンス学部、1994 年
• レーン A. ヘマスパアンドラ、荻原 光則、「複雑性理論の手引き」、理論計算機科学テキスト、EATCS シリーズ、Springer、2002 年、ISBN  3-540-67419-5、294ページ
• Lane A. Hemaspaandra、Leen Torenvliet、「半実行可能アルゴリズムの理論」、Monographs in theory computer science、Springer、2003、ISBN 3-540-42200-5、1ページ 
• Ker-I Ko、「離散複雑性理論の技術を数値計算に適用する」、 Ronald V. Book (編)、「複雑性理論の研究」、理論計算機科学の研究ノート、Pitman、1986 年、ISBN 0-470-20293-9、p. 40 
• C. Jockusch jr (1968). 「半再帰集合と正の還元可能性」(PDF) . Trans. Amer. Math. Soc. 137 (2): 420– 436. doi :10.1090/S0002-9947-1968-0220595-7.