In der Mathematik und der theoretischen Informatik bezeichnet das Semi-Mitgliedschaftsproblem einer Menge die Frage, welches von zwei möglichen Elementen logisch gesehen eher zu dieser Menge gehört; alternativ, bei zwei Elementen, von denen mindestens eines in der Menge enthalten ist, geht es darum, das Element von dem Nicht-Element zu unterscheiden.

Das Problem der Halbzugehörigkeit kann deutlich einfacher sein als das Zugehörigkeitsproblem. Betrachten wir beispielsweise die Menge S ( x ) der Binärstrings endlicher Länge, die die dyadischen rationalen Zahlen kleiner als eine feste reelle Zahl x repräsentieren . Das Problem der Halbzugehörigkeit für ein Paar von Strings wird gelöst, indem man den String auswählt, der die kleinere dyadische rationale Zahl repräsentiert. Denn wenn genau einer der Strings ein Element ist, muss es der kleinere sein, unabhängig vom Wert von x . Allerdings ist die Sprache S ( x ) möglicherweise keine rekursive Sprache , da es überabzählbar viele solcher x gibt , aber nur abzählbar viele rekursive Sprachen.

Eine Funktion f auf geordneten Paaren ( x , y ) ist ein Selektor für eine Menge S , wenn f ( x , y ) gleich x oder y ist und wenn f ( x , y ) genau dann in S liegt , wenn mindestens eines der Elemente x oder y in S liegt . Eine Menge heißt semi-rekursiv , wenn sie einen rekursiven Selektor besitzt, und P-selektiv oder semi-zulässig, wenn sie semi-rekursiv ist und einen Selektor mit polynomieller Laufzeit besitzt .

Semi-fasible Mengen haben kleine Schaltkreise ; sie befinden sich in der erweiterten niedrigen Hierarchie ; und können nicht NP-vollständig sein, es sei denn , P=NP .

Referenzen

  • Derek Denny-Brown, „Semi-Membership-Algorithmen: Einige neuere Fortschritte“, Technischer Bericht , Fachbereich Informatik der Universität Rochester, 1994
  • Lane A. Hemaspaandra, Mitsunori Ogihara, „The complexity theory companion“, Texte zur theoretischen Informatik , EATCS-Reihe, Springer, 2002, ISBN 3-540-67419-5Seite 294
  • Lane A. Hemaspaandra, Leen Torenvliet, „Theorie semi-machbarer Algorithmen“, Monographien zur theoretischen Informatik , Springer, 2003, ISBN 3-540-42200-5Seite 1
  • Ker-I Ko, „Anwendung von Techniken der diskreten Komplexitätstheorie auf numerische Berechnungen“ in Ronald V. Book (Hrsg.), „Studien zur Komplexitätstheorie“, Forschungsnotizen zur theoretischen Informatik , Pitman, 1986, ISBN 0-470-20293-9, S. 40
  • C. Jockusch jr (1968). „Semirekursive Mengen und positive Reduzierbarkeit“ (PDF) . Trans. Amer. Math. Soc. 137 (2): 420–436 . doi : 10.1090/S0002-9947-1968-0220595-7 .