<p>In the paper <em>The complexity of tensor calculus</em> by C. Damm, M. Holzer and P. McKenzie (<a href="https://ieeexplore.ieee.org/document/856737" rel="noreferrer">link</a>), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor formulae over <span class="math-container">$ \mathbb{N} $</span>, i.e., the semiring of natural numbers including zero. With that, the authors reached the conclusion that &quot;For any infinite field <span class="math-container">$ \mathbb{F} $</span>, <span class="math-container">$ \operatorname{val}_{\mathbb{F}} $</span> is #P-hard under polytime Turing reductions.&quot; by claiming that &quot;<span class="math-container">$ \mathbb{N} $</span> is embedded in every infinite field.&quot; (See Corollary 10 in the original paper)</p>
<p>My question is exactly about the last sentence. Don't there exist cases where an infinite field has a finite characteristic? Or is there any way to prove Corollary 10 without following this line of reasoning?</p>

CC BY-SA 4.0
2021-03-18T07:53:41.490Z
An infinite field certainly can have finite characteristic, such as the algebraic closure $\widetilde{\mathbb F}_p$ or the simple transcendental extension $\mathbb F_p(t)$. I don’t know the context it appears in in this paper, perhaps their methods somehow can be adapted to these cases, or something. But on its own, this definitely sounds quite suspicious.
Emil Jeřábek
CC BY-SA 4.0
2021-03-18T08:34:57.383Z
Yes I agree with you. Thank you for your comment. Perhaps someone familiar with counting complexity related to tensor-formula-related problems can provide any information over the correctness and the rigorous proof of the statement made by the authors?
Conn-CaoYK
CC BY-SA 4.0
2021-03-18T11:33:19.470Z
(In the [full paper](https://doi.org/10.1007/s00037-000-0170-4), the same claim is made as Corollary 4.6.) The more I think about it, it looks as an error. Presumably, the same argument shows that permanent of 0–1 matrices modulo $p$ reduces to $\mathrm{val}_F$ when $F$ has characteristic $p$, but this does not give #P-hardness (only $\oplus_pP$-hardness for odd $p$, and nothing much for $p=2$).
Emil Jeřábek
CC BY-SA 4.0
2021-03-18T12:08:36.227Z
Thank you for your comments on the implications when the field is of odd prime characteristic. I didn't know the complexity of permanent of 0/1 matrices on such a field before.
Conn-CaoYK
<counting-complexity><reductions>
The complexity of tensor formula evaluation problem over an infinite field
Conn-CaoYK
# The complexity of tensor formula evaluation problem over an infinite field

(Asked by: username_0 on 2021-03-18)

In the paper *The complexity of tensor calculus* by C. Damm, M. Holzer and P. McKenzie ([link](https://ieeexplore.ieee.org/document/856737)), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor formulae over $ \mathbb{N} $, i.e., the semiring of natural numbers including zero. With that, the authors reached the conclusion that "For any infinite field $ \mathbb{F} $, $ \operatorname{val}\_{\mathbb{F}} $ is #P-hard under polytime Turing reductions." by claiming that "$ \mathbb{N} $ is embedded in every infinite field." (See Corollary 10 in the original paper)

My question is exactly about the last sentence. Don't there exist cases where an infinite field has a finite characteristic? Or is there any way to prove Corollary 10 without following this line of reasoning?

**Tags:** counting-complexity, reductions
> **Comments:**
> **username_1**: An infinite field certainly can have finite characteristic, such as the algebraic closure $\widetilde{\mathbb F}_p$ or the simple transcendental extension $\mathbb F_p(t)$. I don’t know the context it appears in in this paper, perhaps their methods somehow can be adapted to these cases, or something. But on its own, this definitely sounds quite suspicious.  
> **username_0**: Yes I agree with you. Thank you for your comment. Perhaps someone familiar with counting complexity related to tensor-formula-related problems can provide any information over the correctness and the rigorous proof of the statement made by the authors?  
> **username_1**: (In the [full paper](https://doi.org/10.1007/s00037-000-0170-4), the same claim is made as Corollary 4.6.) The more I think about it, it looks as an error. Presumably, the same argument shows that permanent of 0–1 matrices modulo $p$ reduces to $\mathrm{val}_F$ when $F$ has characteristic $p$, but this does not give #P-hardness (only $\oplus_pP$-hardness for odd $p$, and nothing much for $p=2$).  
> **username_0**: Thank you for your comments on the implications when the field is of odd prime characteristic. I didn't know the complexity of permanent of 0/1 matrices on such a field before.  

---

## 0 answers

