<p>The collection of tensors of a given rank, or even of tensors with rank at most $k$ is not a (Zariski-)closed set, so it cannot be described as the vanishing locus of any set of polynomials, regardless of their complexity. (However, over finite fields tensor-rank is $NP$-complete and over $\mathbb{Q}$ it is $NP$-hard but not known to be in $NP$. But these are the usual Boolean classes, not the Valiant analogues.)</p>

<p>The closure of the the set of tensors of rank at most $k$ is the set of tensors of <em>border</em>-rank at most $k$. Call a set of polynomials whose vanishing locus is the set of tensors of border-rank at most $k$ a system of (set-theoretic) defining equations for border rank at most $k$. Such defining equations are known for small $k$, but for most $k$ finding such defining equations is a long-standing open problem, related the border-rank and multiplicative complexity of matrix multiplication.</p>

<p>See Landsberg's Bulletin article <a href="http://www.ams.org/journals/bull/2008-45-02/S0273-0979-08-01176-2/">Geometry and the complexity of matrix multiplication</a> for an introduction and some references, and see Landsberg's recent book <a href="http://www.ams.org/bookstore-getitem/item=gsm-128">Tensors: Geometry and Applications</a> (<a href="http://www.math.tamu.edu/~jml/Tbookintro.pdf">freely available introduction</a>) for all that is known about defining equations for border-rank.</p>

CC BY-SA 3.0
2012-07-11T03:47:08.547Z
Thanks for answer. I would like just to note that it will be O.K. if $f(T)=0$ for $T$ of high rank I need only that $f(T)=0$ on all small rank tensors.
Klim
CC BY-SA 3.0
2012-07-11T04:18:31.563Z
@Klim: Presumably you also want $f$ to be not the zero function... Beyond that, is there some additional nontriviality condition you want $f$ to have, for example, that $f$ depend on all $n^{3}$ of its inputs? (If so you might add that clarification to the question.)
Joshua Grochow
CC BY-SA 3.0
2012-07-11T05:09:45.753Z
No $f$ may not depend on all its inputs.
Klim
CC BY-SA 3.0
2012-07-10T22:37:05.180Z
2012-07-10T22:37:05.180Z
Joshua Grochow
<p>Is it known if tensor rank of three dimensional tensors lies in VNP (non deterministic valiant class)? If yes, what is known about high dimensional tensor rank?</p>

<p>In fact I am interested in much more simple problem. I would like  to know if one can construct class non-zero polynomials $f_n$ which lies in VNP, in $n^3$ variables such that $f_i(T)=0$ if tensor rank of $T$ less than $n^{1.9}$.
For simplicity let us assume that we are working over $\mathbb{C}$. </p>

<p>I would like to mention that it is O.K. if $f_i(T)=0$ for $T$ of high rank only what I need is that $f_i(T)=0$ for all small rank tensors. </p>

CC BY-SA 3.0
2012-07-10T21:45:00.120Z
Related question: [Complexity of Tensor Rank over an Infinite Field](http://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field)
Tyson Williams
<cc.complexity-theory><algebraic-complexity>
Is tensor rank is in VNP?
Klim
# Is tensor rank is in VNP?

(Asked by: username_0 on 2012-07-10)

Is it known if tensor rank of three dimensional tensors lies in VNP (non deterministic valiant class)? If yes, what is known about high dimensional tensor rank?

In fact I am interested in much more simple problem. I would like to know if one can construct class non-zero polynomials $f\_n$ which lies in VNP, in $n^3$ variables such that $f\_i(T)=0$ if tensor rank of $T$ less than $n^{1.9}$.
For simplicity let us assume that we are working over $\mathbb{C}$.

I would like to mention that it is O.K. if $f\_i(T)=0$ for $T$ of high rank only what I need is that $f\_i(T)=0$ for all small rank tensors.

**Tags:** cc.complexity-theory, algebraic-complexity
> **Comments:**
> **username_1**: Related question: [Complexity of Tensor Rank over an Infinite Field](http://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field)  

---

## 1 answers

### Answer by username_2 on 2012-07-10. Score: 9 | Accepted answer

The collection of tensors of a given rank, or even of tensors with rank at most $k$ is not a (Zariski-)closed set, so it cannot be described as the vanishing locus of any set of polynomials, regardless of their complexity. (However, over finite fields tensor-rank is $NP$-complete and over $\mathbb{Q}$ it is $NP$-hard but not known to be in $NP$. But these are the usual Boolean classes, not the Valiant analogues.)

The closure of the the set of tensors of rank at most $k$ is the set of tensors of *border*-rank at most $k$. Call a set of polynomials whose vanishing locus is the set of tensors of border-rank at most $k$ a system of (set-theoretic) defining equations for border rank at most $k$. Such defining equations are known for small $k$, but for most $k$ finding such defining equations is a long-standing open problem, related the border-rank and multiplicative complexity of matrix multiplication.

See Landsberg's Bulletin article [Geometry and the complexity of matrix multiplication](http://www.ams.org/journals/bull/2008-45-02/S0273-0979-08-01176-2/) for an introduction and some references, and see Landsberg's recent book [Tensors: Geometry and Applications](http://www.ams.org/bookstore-getitem/item=gsm-128) ([freely available introduction](http://www.math.tamu.edu/~jml/Tbookintro.pdf)) for all that is known about defining equations for border-rank.

> **Comments:**
> **username_0**: Thanks for answer. I would like just to note that it will be O.K. if $f(T)=0$ for $T$ of high rank I need only that $f(T)=0$ on all small rank tensors.  
> **username_2**: @Klim: Presumably you also want $f$ to be not the zero function... Beyond that, is there some additional nontriviality condition you want $f$ to have, for example, that $f$ depend on all $n^{3}$ of its inputs? (If so you might add that clarification to the question.)  
> **username_0**: No $f$ may not depend on all its inputs.  

---

