Um

11

Quero especificar o que significa dar uma álgebra como entrada para um algoritmo e não encontrei muita literatura sobre isso. Então, primeiro quero perguntar se você pode recomendar um livro ou artigo que lide com o tópico de análise de complexidade de álgebras sobre campos e defina claramente o problema de decisão .

Após algumas pesquisas, encontrei algo e quero compartilhá-lo aqui e, além disso, pergunto se as definições fazem sentido e estão em conformidade com a literatura (se houver):

Definição: Let ser um campo e ser um número finito gerado conmutativo -álgebra com aditivo base . Agora, queremos capturar a estrutura multiplicativa da álgebra e, portanto, escrever todos os produtos dos elementos base como uma combinação linear de todos os elementos base: Os são chamados de coeficientes de estrutura . Temos diretamente isso: A F b 1 , , b nF1 i , j , k n : a i j k : b i b j = n k = 1 a i j k b k . a i j k A F [ b 1 , , b nFAFb1,,bnF

1i,j,kn:aijk:bibj=k=1naijkbk.
aijk{(A,B)A,B comutativas  F- álgebras com base  b 1 , b n  e AB}. ϕ:ABϕ(
AF[b1,,bn]/bibjk=1naijkbk1i,jn.
Agora pode-se definir o seguinte problema de decisão: Para especificar um isomorfismo é suficiente para escrever todos os como combinação linear dos elementos de uma base de .
{(A,B)A,B commutative F-algebras with basis b1,bn and AB}.
ϕ:ABBϕ(bi)B

Alguma coisa nesta definição lhe parece estranha ou você acha que alguém pode trabalhar com ela?

Motivação: Minha motivação por trás disso é fornecer uma definição muito clara do problema de decisão para conectá-lo a outros problemas, ou seja, o problema de decidir a equivalência polinomial: Dados dois polinômios , dizemos que é equivalente a se existe uma transformação linear invertível nas variáveis ​​tais que . Em outras palavras, dois polinômios são equivalentes se você puder substituir todas as variáveis ​​por uma combinação linear de todas as variáveis ​​para obter o outro polinômio.f g τ f ( τ ( x 1 ) , , τ ( x n ) ) = g ( x 1 , , x n )f,gF[x1,,xn]fgτf(τ(x1),,τ(xn))=g(x1,,xn)

Não tenho certeza se isso ajuda como motivação, mas a conexão desses problemas é estabelecida através da construção de álgebras comutativas finitamente geradas a partir dos dois polinômios que são isomórficos se e somente se os polinômios forem equivalentes. Para isso, eu queria ter certeza de que o problema de decisão é definido com muita clareza.F

nascermos
fonte
Alguém sabe referências além da que o mhum se vincula ?
nascido

Respostas: