Skip to main content
MathOverflow

Return to Question

edited body
Source Link
aayad
aayad
  • 121
  • 3

Consider the following (NP-complete) problem:

Given a system of polynomials $f_1, f_2, \ldots, f_n \in \mathbb{F}_q[x_1, x_2, \ldots, x_m]$$f_1, f_2, \ldots, f_m \in \mathbb{F}_q[x_1, x_2, \ldots, x_n]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational point (ie., a common solution in $\mathbb{F}_q$).

[Kayal, 2007] (cf. page 80) showed that for a fixed $n$, there is a deterministic algorithm with complexity $\mathsf{poly}(d, m, \log q)$ for the existential question (solvability). He also showed that there is an efficient approximation algorithm for counting the number of solutions.

I was unable to find any recent work in this direction, and was wondering if more has been discovered since 2007. In particular, I am interested in knowing whether there has been any progress with regards to the search problem (deterministic or randomized), perhaps even for the simpler case of $m = 2$$n = 2$.

Consider the following (NP-complete) problem:

Given a system of polynomials $f_1, f_2, \ldots, f_n \in \mathbb{F}_q[x_1, x_2, \ldots, x_m]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational point (ie., a common solution in $\mathbb{F}_q$).

[Kayal, 2007] (cf. page 80) showed that for a fixed $n$, there is a deterministic algorithm with complexity $\mathsf{poly}(d, m, \log q)$ for the existential question (solvability). He also showed that there is an efficient approximation algorithm for counting the number of solutions.

I was unable to find any recent work in this direction, and was wondering if more has been discovered since 2007. In particular, I am interested in knowing whether there has been any progress with regards to the search problem (deterministic or randomized), perhaps even for the simpler case of $m = 2$.

Consider the following (NP-complete) problem:

Given a system of polynomials $f_1, f_2, \ldots, f_m \in \mathbb{F}_q[x_1, x_2, \ldots, x_n]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational point (ie., a common solution in $\mathbb{F}_q$).

[Kayal, 2007] (cf. page 80) showed that for a fixed $n$, there is a deterministic algorithm with complexity $\mathsf{poly}(d, m, \log q)$ for the existential question (solvability). He also showed that there is an efficient approximation algorithm for counting the number of solutions.

I was unable to find any recent work in this direction, and was wondering if more has been discovered since 2007. In particular, I am interested in knowing whether there has been any progress with regards to the search problem (deterministic or randomized), perhaps even for the simpler case of $n = 2$.

edited title
Link
aayad
aayad
  • 121
  • 3

What do we know about efficiently finding a solution to a system of multivariate polynomials over finite fields?

Source Link
aayad
aayad
  • 121
  • 3

What do we know about finding a solution to a system of multivariate polynomials over finite fields?

Consider the following (NP-complete) problem:

Given a system of polynomials $f_1, f_2, \ldots, f_n \in \mathbb{F}_q[x_1, x_2, \ldots, x_m]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational point (ie., a common solution in $\mathbb{F}_q$).

[Kayal, 2007] (cf. page 80) showed that for a fixed $n$, there is a deterministic algorithm with complexity $\mathsf{poly}(d, m, \log q)$ for the existential question (solvability). He also showed that there is an efficient approximation algorithm for counting the number of solutions.

I was unable to find any recent work in this direction, and was wondering if more has been discovered since 2007. In particular, I am interested in knowing whether there has been any progress with regards to the search problem (deterministic or randomized), perhaps even for the simpler case of $m = 2$.