Jaka jest nazwa funkcji

Niech będzie językiem if : Σ ⋆ × Σ ⋆ → Σ ⋆ funkcja na dwóch parametrach z właściwością, która dla wszystkich x i y , f zwraca element L wtedy i tylko wtedy, gdy oba x i y są elementami L :$L$$f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$$x$$y$$f$$L$$x$$y$$L$

Pytanie Czy takie funkcje mają nazwę w literaturze?

Poniżej znajdują się zabawne spostrzeżenia. Funkcje te, które będę nazywał „ redukcjami łączącymi ”, mogą być konstruowane dla kompletnych problemów różnych klas złożoności. Na przykład dla weź funkcję f ( ψ , ϕ ) = ψ ∧ ϕ . Analogicznie możemy rozważyć „ redukcje rozłączne ”, tak że g ( ψ , ϕ ) = ψ ∨ ϕ jest redukcją rozłączną w stosunku do S A $L=SAT$$f(\psi, \phi)=\psi\wedge\phi$$g(\psi,\phi)=\psi\vee\phi$$SAT$. Te dwie redukcje działają również dobrze w stosunku do formuł liczbowych boolowskich, więc działają również na wszystkich poziomach hierarchii wielomianowej i na PSPACE.

Łatwo jest zbudować zarówno łączne, jak i rozłączne redukcje dla języków L i NL-Complete DSTCON i USTCON: Biorąc pod uwagę dwa wykresy, i dwie pary wierzchołków, ( u , v ) , ( x , y ) , skonstruuj nowy wykreślić, biorąc łączenie rozłączne G ∪ H , dodaj dwa węzły s , t i dodaj krawędzie ( s , u ) , ( v , x ) , ( y , t $G, H$$(u,v), (x,y)$$G\cup H$$s,t$$(s,u),(v,x),(y,t)$. Rozłączna redukcja ustawia te dwa wykresy równolegle, a nie szeregowo.

W przypadku izomorfizmu grafowego istnieje redukcja łączna, ale oczywiście nie występuje redukcja łącząca. I odwrotnie, istnieje redukcja dysjunkcyjna dla problemu nietrywialnego automorfizmu grafów, ale nie udało mi się znaleźć redukcji koniunkturalnej. Zaskoczyło mnie to, ponieważ myślałem, że te problemy są do pewnego stopnia takie same, a potem nauczyłem się czegoś nowego na temat izomorfizmu grafów!

Jak oczywiste ostatnim etapie, można rozważyć „ sprzężone redukcji ”, funkcje takie, że . Znalezienie takiej redukcji dla grafowego izomorfizmu pokazałoby, że jest w CoNP. Nie mogłem znaleźć ani koniunkcyjnego, ani rozłącznego, ani koniugatu zmniejszenia dla wersji decyzyjnej Faktoringu.$f(x)\in L \iff x \not\in L$

Zazwyczaj są one nazywane funkcjami AND. (Nie żartuję.) Rzeczywiście, ta koncepcja była wcześniej rozważana i tak nazywają ją ludzie. Zobacz na przykład książkę Koblera, Schoninga i Torana o Graph Iso, gdzie mówią o funkcjach AND i OR dla GI. I, nawiasem mówiąc, nie jest OR-funkcja dla GI (ibid.).

Pytanie o funkcję AND dla automorfizmu grafów jest, jak sądzę, wciąż otwarte :) (jak stwierdzono w powyższej książce).

Na podstawie ostatniego akapitu rodzaj redukcji, o której mówisz, można również uogólnić na tak zwane redukcje „tabeli prawdy” lub „tt”. Są to nieadaptacyjne redukcje Turinga (zapytania są ustalane przez dane wejściowe, ale nie mogą zależeć od odpowiedzi na poprzednie zapytania). Na przykład redukcja rodzaju negacji w ostatnim akapicie to redukcja o 1 tt (1 = liczba zapytań).