Qual é o nome de uma função

Seja uma linguagem ef : function ⋆ × Σ ⋆ → Σ ⋆ uma função em dois parâmetros com a propriedade que para todos x e y , f retorna um elemento de L se e somente se x e y forem elementos de L :$L$$f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$$x$$y$$f$$L$$x$$y$$L$

Pergunta Essas funções têm um nome na literatura?

A seguir, algumas observações divertidas. Essas funções, que chamarei de " reduções conjuntivas ", podem ser construídas para os problemas completos de uma variedade de classes de complexidade. Por exemplo, para , use a função f ( ψ , ϕ ) = ψ ∧ ϕ . Analogamente, podemos considerar " reduções disjuntivas ", de modo que g ( ψ , ϕ ) = ψ ∨ ϕ é uma redução disjuntiva sobre S A $L=SAT$$f(\psi, \phi)=\psi\wedge\phi$$g(\psi,\phi)=\psi\vee\phi$$SAT$. Essas duas reduções também funcionam bem com fórmulas booleanas quantificadas, portanto também funcionam para todos os níveis da hierarquia polinomial e para o PSPACE.

É fácil construir reduções conjuntivas e disjuntivas para as linguagens L e NL-Complete DSTCON e USTCON: Dados dois gráficos, e dois pares de vértices, ( u , v ) , ( x , y ) , construa uma nova gráfico tomando a união disjunta G ∪ H , adicione dois nós s , te adicione arestas ( s , u ) , ( v , x ) , ( y , t $G, H$$(u,v), (x,y)$$G\cup H$$s,t$$(s,u),(v,x),(y,t)$. Uma redução disjuntiva coloca esses dois gráficos em paralelo, e não em série.

Existe uma redução conjuntiva para o isomorfismo gráfico, mas obviamente não existe redução disjuntiva. Por outro lado, existe uma redução disjuntiva para o problema de Automorfismo de gráfico não trivial, mas não foi possível encontrar uma redução conjuntiva. Isso me surpreendeu, porque pensei que esses problemas eram, de certa forma, o mesmo, e então eu aprendi algo novo sobre o isomorfismo de gráficos!

Como um último passo óbvio, pode-se considerar " reduções conjugadas ", funções tais que $f(x)\in L \iff x \not\in L$

Eles são normalmente chamados de funções AND. (Não estou brincando.) Na verdade, esse conceito já foi considerado antes, e é assim que as pessoas os chamam. Veja, por exemplo, o livro de Kobler, Schoning e Toran no Graph Iso, onde eles falam sobre funções AND e OR para GI. E, a propósito, não é um OR-função para GI (ibid.).

A questão de uma função AND para o automorfismo gráfico é, acredito, ainda em aberto :) (como afirmado no livro acima).

Com base no seu último parágrafo, o tipo de redução de que você está falando também pode ser generalizado para o que é chamado de reduções "tabela da verdade" ou "tt". Essas são reduções de Turing não adaptáveis ​​(as consultas são fixadas pela entrada, mas não podem depender da resposta às consultas anteriores). Por exemplo, o tipo de redução de negação em seu último parágrafo é uma redução de 1 tt (1 = número de consultas).