The Complexity of Tensor Rank
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2016
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911752608808960 |
|---|---|
| author | Schaefer, Marcus Stefankovic, Daniel |
| author_facet | Schaefer, Marcus Stefankovic, Daniel |
| contents | We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by Håstad~\cite{H90}. The hardness proof also implies an algebraic universality result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1612_04338 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | The Complexity of Tensor Rank Schaefer, Marcus Stefankovic, Daniel Computational Complexity We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by Håstad~\cite{H90}. The hardness proof also implies an algebraic universality result. |
| title | The Complexity of Tensor Rank |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/1612.04338 |