Semi-členství - Semi-membership

v matematika a teoretická informatika, problém polovičního členství pro množinu je problém rozhodnout, který ze dvou možných prvků logicky pravděpodobněji patří do této množiny; alternativně, vzhledem ke dvěma prvkům, z nichž alespoň jeden je v množině, k odlišení člena od nečlenu.

Problém s částečným členstvím může být výrazně jednodušší než problém s členstvím. Zvažte například sadu S(X) binárních řetězců konečné délky představujících dyadické racionály menší než nějaké pevné reálné číslo X. Problém semi-členství pro dvojici řetězců je vyřešen převzetím řetězce představujícího menší dyadický racionální, protože pokud je právě jeden z řetězců prvkem, musí být menší, bez ohledu na hodnotu X. Avšak jazyk S(X) nemusí být ani a rekurzivní jazyk, protože takových je nespočetně mnoho X, ale jen spočetně mnoho rekurzivních jazyků.

Funkce F na objednané páry (X,y) je volič za sadu S -li F(X,y) se rovná buď X nebo y a pokud F(X,y) je v S kdykoli alespoň jeden z X, y je v S. Sada je semi-rekurzivní pokud má rekurzivní volič a je P-selektivní nebo částečně proveditelné pokud je semi-rekurzivní s a polynomiální čas volič.

Polo-proveditelné sady mají malé obvody; jsou v rozšířená nízká hierarchie; a nemůže být NP-kompletní pokud P = NP.

Reference

  • Derek Denny-Brown, „Algoritmy polovičního členství: některé nedávné pokroky“, Technická zpráva, University of Rochester Department of Computer Science, 1994
  • Lane A. Hemaspaandra, Mitsunori Ogihara, "Společník teorie složitosti", Texty z teoretické informatiky, Řada EATCS, Springer, 2002, ISBN  3-540-67419-5, strana 294
  • Lane A. Hemaspaandra, Leen Torenvliet, „Teorie částečně proveditelných algoritmů“, Monografie v teoretické informatice, Springer, 2003, ISBN  3-540-42200-5, Strana 1
  • Ker-I Ko, „Aplikování technik teorie diskrétní složitosti na numerické výpočty“ v Ronald V. Book, ed., „Studies in theory of complexity“, Poznámky k výzkumu v teoretické informatice, Pitman, 1986, ISBN  0-470-20293-9, str.40
  • C. Jockusch jr (1968). „Semirekurzivní množiny a pozitivní redukovatelnost“ (PDF). Trans. Amer. Matematika. Soc. 137: 420–436.