Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory

Understand

We study the variety membership testing problem in the case when the variety is given as an orbit closure and the ambient space is the set of all 3-tensors.

• The first variety that we consider is the slice rank variety, which consists of all 3-tensors of slice rank at most $r$.
• We show that the membership testing problem for the slice rank variety is $\NP$-hard.
• While the slice rank variety is a union of orbit closures, we define another variety, the minrank variety, expressible as a single orbit closure.