Częściowe członkostwo

W matematyce i informatyce teoretycznej problem półczłonkostwa dla zbioru to problem decydowania, który z dwóch możliwych elementów ma logicznie większe prawdopodobieństwo przynależności do tego zbioru; alternatywnie, biorąc pod uwagę dwa elementy, z których co najmniej jeden jest w zbiorze, aby odróżnić członka od niebędącego członkiem.

Problem półczłonkostwa może być znacznie łatwiejszy niż problem członkostwa. Rozważmy na przykład zbiór S ( x ) ciągów binarnych o skończonej długości reprezentujących wymierne diady mniejsze niż pewna ustalona liczba rzeczywista x . Problem półczłonkostwa dla pary strun rozwiązuje się, biorąc strunę reprezentującą mniejszy wymierny diadyczny, ponieważ jeśli dokładnie jedna ze strun jest elementem, to musi być mniejsza, niezależnie od wartości x . Jednak język S ( x ) może nawet nie być a język rekurencyjny , ponieważ istnieje niezliczona ilość takich x , ale tylko przeliczalnie wiele języków rekurencyjnych.

Funkcja f na uporządkowanych parach ( x , y ) jest selektorem dla zbioru S , jeśli f ( x , y ) jest równe x lub y i jeśli f ( x , y ) jest w S , gdy co najmniej jeden z x , y jest w S. Zbiór jest półrekurencyjny, jeśli ma selektor rekurencyjny i jest P-selektywny lub częściowo wykonalny, jeśli jest pół-rekurencyjny z wielomianowym selektorem czasu .

Zestawy częściowo wykonalne mają małe obwody ; znajdują się w rozszerzonej niższej hierarchii ; i nie może być NP-zupełny , chyba że P=NP .

• Derek Denny-Brown, „Algorytmy półczłonkostwa: niektóre ostatnie postępy”, raport techniczny , Wydział Informatyki Uniwersytetu Rochester, 1994
•   Lane A. Hemaspaandra, Mitsunori Ogihara, „towarzysz teorii złożoności”, Teksty z informatyki teoretycznej , seria EATCS, Springer, 2002, ISBN 3-540-67419-5 , strona 294
•   Lane A. Hemaspaandra, Leen Torenvliet, „Teoria półwykonalnych algorytmów”, Monografie w informatyce teoretycznej , Springer, 2003, ISBN 3-540-42200-5 , strona 1
•   Ker-I Ko, „Stosowanie technik teorii złożoności dyskretnej do obliczeń numerycznych” w Ronald V. Book (red.), „Studia z teorii złożoności”, notatki badawcze z informatyki teoretycznej , Pitman, 1986, ISBN 0-470-20293 -9 , s.40
• C. Jockusch jr (1968). „Zestawy półrekurencyjne i pozytywna redukowalność” (PDF) . Trans. Amer. Matematyka soc. 137 : 420–436.