Wie heißt eine Funktion

Let eine Sprache und sein eine Funktion von zwei Parametern mit der Eigenschaft , dass für alle und , kehrt ein Element der genau dann, wenn sowohl als auch Elemente von :f : & Sigma; ⋆ × & Sigma; ⋆ → & Sigma; ⋆ x y f L x y $L$$f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$$x$$y$$f$$L$$x$$y$$L$

Frage Haben solche Funktionen in der Literatur einen Namen?

Es folgen einige amüsante Beobachtungen. Diese Funktionen, die ich " konjunktive Reduktionen " nennen werde, können für die vollständigen Probleme einer Vielzahl von Komplexitätsklassen konstruiert werden. Nehmen Sie zum Beispiel für die Funktion . Analog können wir " disjunktive Reduktionen " betrachten, so dass eine disjunktive Reduktion gegenüber . Diese beiden Reduktionen funktionieren auch gut über quantifizierte Boolesche Formeln, sodass sie auch für alle Ebenen der Polynomhierarchie und für PSPACE funktionieren.f ( ψ , φ ) = ψ ∧ φ g ( ψ , φ ) = ψ ∨ φ S A $L=SAT$$f(\psi, \phi)=\psi\wedge\phi$$g(\psi,\phi)=\psi\vee\phi$$SAT$

Es ist einfach, sowohl konjunktive als auch disjunktive Reduktionen für die L- und NL-vollständigen Sprachen DSTCON und USTCON zu konstruieren: Wenn zwei Graphen und zwei Eckpunktpaare , konstruieren Sie eine neue Zeichnen Sie durch Nehmen der disjunkten Vereinigung zwei Knoten und fügen Sie die Kanten . Durch eine disjunktive Reduktion werden diese beiden Graphen parallel und nicht in Reihe geschaltet.( u , v ) , ( x , y ) G ∪ H s , t ( s , u ) , ( v , x ) , ( y , t $G, H$$(u,v), (x,y)$$G\cup H$$s,t$$(s,u),(v,x),(y,t)$

Für den Graph-Isomorphismus existiert eine konjunktive Reduktion, aber offensichtlich existiert keine disjunktive Reduktion. Umgekehrt gibt es eine disjunktive Reduktion für das Problem des nichttrivialen Graphautomorphismus, aber ich konnte keine konjunktive Reduktion finden. Das überraschte mich, weil ich dachte, diese Probleme wären auf einer bestimmten Ebene gleich, und dann hatte ich etwas Neues über den Graphisomorphismus gelernt!

Als offensichtlich letzten Schritt kann man "betrachten Konjugat Verringerungen ", funktioniert so , daß . Das Finden einer solchen Reduktion für den Graphisomorphismus würde zeigen, dass es sich um coNP handelt. Ich konnte weder eine konjunktive noch eine disjunktive oder konjugierte Reduktion für die Entscheidungsversion von Factoring finden.$f(x)\in L \iff x \not\in L$

Sie werden typischerweise als UND-Funktionen bezeichnet. (Ich scherze nicht.) In der Tat wurde dieses Konzept schon früher in Betracht gezogen, und so nennen die Leute sie. Siehe zum Beispiel das Buch von Kobler, Schoning und Toran über Graph Iso, in dem sie über AND- und OR-Funktionen für GI sprechen. Übrigens gibt es eine OR-Funktion für GI (ebenda).

Die Frage nach einer UND-Funktion für den Graph-Automorphismus ist meines Erachtens noch offen :) (wie im obigen Buch angegeben).

Basierend auf Ihrem letzten Absatz kann die Art der Reduzierung, von der Sie sprechen, auch auf sogenannte "Wahrheitstabellen" - oder "tt" -Reduktionen verallgemeinert werden. Dies sind nicht adaptive Turing-Reduzierungen (die Abfragen werden durch die Eingabe festgelegt, können jedoch nicht von der Antwort auf vorherige Abfragen abhängen). Beispielsweise ist die Negationsreduktion in Ihrem letzten Absatz eine 1-tt-Reduktion (1 = Anzahl der Abfragen).