A classificação do tensor está no VNP?

8

Sabe-se se a classificação tensorial dos tensores tridimensionais se encontra no VNP (classe valente não determinística)? Se sim, o que se sabe sobre a classificação tensorial de alta dimensão?

Na verdade, estou interessado em um problema muito mais simples. Gostaria de saber se é possível construir polinômios diferentes de zero que se encontra no VNP, em variáveis ​​tais que se o tensor de menor que . Para simplificar, vamos assumir que estamos trabalhando em .fnn3fi(T)=0Tn1.9C

Gostaria de mencionar que não há problema em que para de classificação alta apenas o que eu preciso é que para todos os tensores de classificação pequena.fi(T)=0Tfi(T)=0

Klim
fonte
4
Questão relacionada: Complexidade do Tensor Posto sobre um campo infinito
Tyson Williams

Respostas:

9

A coleção de tensores de uma determinada classificação, ou mesmo de tensores com classificação no máximo não é um conjunto fechado (Zariski-); portanto, não pode ser descrito como o local de fuga de qualquer conjunto de polinômios, independentemente de sua complexidade. (No entanto, sobre campos finitos, o tensor-rank é completo e acima de é difícil, mas não se sabe que esteja no . Mas essas são as classes booleanas usuais, não os análogos Valiant.)kNPQNPNP

O fechamento do conjunto de tensores de classificação no máximo é o conjunto de tensores de fronteira - no máximo . Chame um conjunto de polinômios cujo locus de fuga é o conjunto de tensores da classificação de borda no máximo um sistema de equações definidoras (teóricas dos conjuntos) para classificação de borda no máximo . Tais equações definidoras são conhecidas por pequeno , mas, para a maioria dos encontrar essas equações definidoras é um problema aberto de longa data, relacionado ao posto de fronteira e à complexidade multiplicativa da multiplicação de matrizes.kkkkkk

Veja o artigo do Landsberg's Bulletin Geometry e a complexidade da multiplicação de matrizes para uma introdução e algumas referências, e veja o livro recente de Landsberg Tensors: Geometry and Applications ( introdução disponível gratuitamente ) para tudo o que se sabe sobre a definição de equações para classificação de fronteira.

Joshua Grochow
fonte
Obrigado pela resposta. Gostaria apenas de observar que tudo ficará bem se para de alto escalão, preciso apenas que em todos os tensores de escalão pequeno. f(T)=0Tf(T)=0
Klim
@ Klim: Presumivelmente, você também quer que não seja a função zero ... Além disso, há alguma condição de não trivialidade adicional que você deseja que tenha, por exemplo, que dependa de todos os de suas entradas? (Se assim você poderia acrescentar que o esclarecimento da questão.)fffn3
Joshua Grochow
Nenhum pode não depender de todas as suas entradas. f
Klim