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 NPcomplete (cf. [Val79, Section 2]). It is a consequence of this fact that MINRANK and other related problems in linear and multilinear algebra are NPcomplete (cf. [BFS99] and [MW]).
Affine variety ($q$) (
AFFVAR
($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$) (
PROJVAR
($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 NPcomplete. I have been pondering:
Problem: What is the complexity of
PROJVAR
($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, Linearsize 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.