Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

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 circuitan algebraic variety for a boolean circuit

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

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

Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
deleted 18 characters in body
Source Link

Consider complexity classes   $\# 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

Consider complexity classes $\# 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

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

To find Finding the number of rational points effectiveeffectively

added 298 characters in body
Source Link
Loading
Notice added Authoritative reference needed by Alexey Milovanov
Bounty Started worth 50 reputation by Alexey Milovanov
Source Link
Loading