Complexidade da classificação de tensores em um campo infinito

22

Um tensor é uma generalização de vetores e matrizes para dimensões mais altas e a classificação de um tensor também generaliza a classificação de uma matriz. Ou seja, a classificação de um tensor é o número mínimo de grau um tensores que soma a T . Um vetor e uma matriz são tensores de grau 1 e 2, respectivamente.TT

Os elementos em vêm de um campo F . Se F é finito, Håstad provou que decidir se a classificação de um tensor de grau 3 é no máximo r é NP-completo, mas quando F é um campo infinito como os racionais Q , ele não dá (ou cita) nenhum limite superior.TFFrFQ

Pergunta: Qual é o limite superior mais conhecido para a complexidade de decidir se a classificação de um tensor de grau 3 acima de Q é no máximo r ?TQr

Tyson Williams
fonte
4
A classificação de um tensor de grau três está acima de ℚ igual à classificação do mesmo tensor acima de ℝ? Nesse caso, o problema pode ser formulado como um caso especial da Teoria Existencial dos Reais e, portanto, está no PSPACE.
Tsuyoshi Ito
8
A idéia no meu comentário anterior não funcionará porque a classificação de um tensor acima de três graus ℚ às vezes é diferente da classificação do mesmo tensor acima de ℝ. Seja {x, y} a base de um espaço vetorial bidimensional e considere o tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Não é difícil ver que sua classificação acima de ℝ é dois, mas sua classificação acima de ℚ é maior que dois. (Este exemplo foi obtido modificando o exemplo que mostra que a classificação acima de ℝ pode ser diferente da classificação acima de ℂ em Kruskal 1989 ).
Tsuyoshi Ito
1
@Tsuyoshi Ito Concordo plenamente. Também não consigo encontrar nenhum limite superior.
Tyson Williams
2
Eu acho que é melhor pedir computabilidade antes da complexidade.
Tsuyoshi Ito
1
O limite superior é trivial que é ce Hastad também prova no mesmo papel que o problema é sobre Q . O seguinte problema mais geral é ce-complete: dado um tensor parcialmente preenchido, existe uma conclusão dele com classificação r ? NP-hardQr
Kaveh

Respostas:

8

Há uma pré-impressão recente sobre isso: http://galton.uchicago.edu/~lekheng/work/np.pdf . Isso mostra que a maioria dos problemas de classificação relacionada com tensores são NP duro durante e C . (Também menciona que decidir a classificação sobre Q é NP difícil.)RCQ

Bart
fonte
Bart, essa pré-impressão (de Hillar e Lim) é fantástica ... muito obrigado.
John Sidles
2
Agradável. No entanto, não entendo esta frase: "Embora o resultado de Håstad se aplique a e F q , essas opções de campos não fazem sentido para todos, exceto um dos problemas acima (a exceção é o sistema bilinear de equações), pois são problemas analíticos apenas bem definidos sobre um campo completo da característica 0. com um valor absoluto. Entre esses campos, R e C são de longe os mais comuns em aplicações e, portanto, restringiremos nossas discussões a esses campos ". QFqRC
Tyson Williams
2
Um dos problemas mencionados na citação acima é a classificação. Esses autores estão dizendo que a classificação de um tensor não está bem definida em relação a ? Q
Tyson Williams
@Tyson: Eu acho que os autores só quero dizer que para muitas aplicações numéricas (equações diferenciais parciais, processamento de sinal), você quer fazer cálculos em ou C . Sendo um analista numérica mim, não vejo muitas aplicações definidas em Q . Eles não significam que a classificação não está bem definido em Q . RCQQ
Bart
1
Embora essa fosse realmente a única resposta (já que John queria que ele fosse um comentário), ainda acredito que essa resposta merece a recompensa, pois forneceu uma referência que mostrou dureza sobre os outros importantes campos infinitos (reais e complexos). Como sugere o título da minha pergunta, estou curioso sobre campos infinitos em geral, mas decidi perguntar sobre os racionais para ter uma pergunta com uma resposta específica. Ainda vou escolher outra pergunta como resposta aceita, se alguém puder fornecer um limite superior (ou mostrar que é incontestável).
Tyson Williams
2

Nota: O texto abaixo foi planejado como um comentário ... definitivamente não é uma resposta, mas sim uma observação pragmática que surgiu de uma reafirmação dos Princípios de ressonância magnética de Charlie Slichter na linguagem da geometria simplética e da teoria quântica da informação (o que retrocede naturalmente nos espaços de estado do produto tensorial de classificação polinomial). Atualmente, temos uma compreensão geométrica parcial desses métodos de classificação de tensores, uma compreensão quântica marginal da informática, essencialmente nenhuma compreensão teórica ou combinatória da complexidade e uma compreensão computacional funcional (mas amplamente empírica).

Estamos muito interessados ​​em ampliar, aprofundar e unificar esse entendimento e, portanto, esperamos que outras pessoas publiquem mais respostas / comentários sobre esse assunto.


C

John Sidles
fonte
1
É fácil afirmar esse teorema? Caso contrário, você pode fornecer um link para uma boa declaração e explicação?
Tyson Williams
1
@ Tyson: Eu acho que John está falando sobre sua experiência em resolver instâncias do problema, e não sobre um teorema.
Joe Fitzsimons
1
Você perguntou a ele sobre um teorema, e ele não parece estar falando sobre um. Eu apenas pensei que você o tivesse entendido mal.
Joe Fitzsimons
2
Na verdade, pensei ter postado um comentário e fiquei surpreso ao vê-lo aparecer como resposta. Doh! Acabei de editá-lo para adicionar uma referência, mas ainda está muito longe de ser uma resposta satisfatória. Uma ótima pergunta de Tyson Williams! :)
John Sidles
1
@ Joe Ele mencionou o teorema da curvatura bissecional holomórfica de Goldberg e Kobayashi, então eu perguntei a ele sobre isso. Não tenho certeza se isso significa que eu o entendi mal ou não.
Tyson Williams