Takunari Miyazaki (Trinity College, Hartford, Connecticut)
Let $\mathbf{F}$ be a finite field of order $q\gt 0$. An affine $\ell$-space over $\mathbf{F}$, denoted by $\mathbf{A}^{\ell} = \mathbf{F}^{\ell}$, is the set of all $\ell$-tuples of elements of $\mathbf{F}$. For a polynomial $f \in \mathbf{F} [X_1, \ldots, X_{\ell}]$, let $Z(f)$ denote the {\em zeros} of $f$ in $\mathbf{A}^{\ell}$, i.e.,
\[Z(f) = \{ (\alpha_1, \ldots, \alpha_{\ell}) \in \mathbf{A}^{\ell} : f(\alpha_1, \ldots, \alpha_{\ell}) = 0 \}.\]The following problem is NP-complete (cf. [Val79, Section 2]). It is a consequence of this fact that MIN-RANK and other related problems in linear and multilinear algebra are NP-complete (cf. [BFS99] and [MW]).
Affine variety ($q$) (
AFF-VAR($q$))
- Instance: a polynomial $f \in \mathbf{F}[X_1, \ldots, X_\ell]$.
- Question: $Z(f) \ne \emptyset$?
A projective $\ell$-space over $\mathbf{F}$, denoted by $\mathbf{P}^{\ell} = \mathbf{P}(\mathbf{F})^{\ell}$, is the set of equivalence classes of $(\ell + 1)$-tuples $(\alpha_0, \alpha_1, \ldots, \alpha_\ell)$, where each $\alpha_i \in \mathbf{F}$, not all zeros, under the relation defined by $(\alpha_0, \alpha_1, \ldots, \alpha_\ell) \sim (\lambda\alpha_0, \lambda\alpha_1, \ldots, \lambda\alpha_\ell)$ for all $\lambda \in \mathbf{F}$, $\lambda \ne 0$. An element of $\mathbf{P}^{\ell}$ is often identified by co"ordinate ratios $(\beta_1 : \cdots : \beta_{\ell})$, where each $\beta_i \in \mathbf{F}$. For a homogeneous polynomial $f \in \mathbf{F}[X_1, \ldots, X_{\ell}]$, the {\em zeros} of $f$ in $\mathbf{P}^{\ell}$ is defined by
\[Z(f) = \{ (\beta_1 : \cdots : \beta_{\ell}) \in \mathbf{P}^{\ell} : f(\beta_1, \ldots, \beta_{\ell}) = 0 \}.\]Now, consider:
Projective variety ($q$) (
PROJ-VAR($q$))
- Instance: a homogenous polynomial $f \in \mathbf{F}[X_1, \ldots, X_{\ell}]$.
- Question: $Z(f) \ne \emptyset$?
To my knowledge, little is known about the complexity of this problem. I have not seen any proof that it is NP-complete. I have been pondering:
Problem: What is the complexity of
PROJ-VAR($q$)?
This originally arose while working with J.B. Wilson to investigate the complexity of testing singularity of bilinear maps (cf. [MW]).
-
[BFS99] J. F. Buss, G. S. Frandsen and J. O. Shallit, The computational complexity of some problems of linear algebra, J. Comput. System Sci. 58 (1999), 572–596.
-
[MW] T. Miyazaki and J. B. Wilson, Linear-size reductions and completeness in algebra, preprint.
-
[Val79] L. G. Valiant, Completeness classes in algebra, Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, Apr. 30–May 2, 1979, ACM, New York, 1979, pp. 249–261.
Additional Questions?
If you have additional questions, feel free to reach out to a maintainer / contributor on the contact page.
