3
$\begingroup$

Consider $\# P$ and $\oplus P$.

There is a $\# P$-hard problem: to find number of rational solutions of a system of polynomial equations over $\mathbb{F}_2$. The corresponding $\oplus P$-hard problem - to find this number modulo 2.

However for algebraic variety $X$ there is Lefschetz formula for finding number of rational points: $\sum_i (-1)^i \mathrm{Tr}(F^*, H_c^i(X, \mathbb{Q}_l))$ - here $F$ is Frobenius morphism.

If we change $l$-adic cohomology to de Rham cohomology we will get the number of rational points modulo 2.

So, to solve problems in $\# P$ and $\oplus P$ it is enough to find some traces of linear operators! :). I understand that it is not very simple because corresponding spaces are defined rather hard. But still:

Does anybody try to use it to prove that $\# P$ or $\oplus P$ belongs to $NP$ or $AM$ (https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol)? What is an encumbrance to do this? Can we use it to find some effective algorithms of finding number of rational points in some cases?

UPD: well, I have understood an encumbrance: theorems of algebraic geometry often deals with irreducible algebraic varieties not with just algebraic sets. So, it is seems more reasonably to solve this problem: an algebraic variety for a boolean circuit

Improve this question
$\endgroup$
3
  • $\begingroup$ What is rational solution over $\mathbb{F}_2$ ? $\endgroup$
    – Max Alekseyev
    Apr 21, 2016 at 19:06
  • $\begingroup$ a solution of kind $(x_1, \ldots, x_n)$ where all $x_i \in \mathbb{F}_2$ $\endgroup$
    – Alexey Milovanov
    Apr 21, 2016 at 19:46
  • $\begingroup$ @Turbo, no, I can not find it... $\endgroup$
    – Alexey Milovanov
    Apr 23, 2016 at 12:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.