Some NP Complete Problems Based on Algebra and Algebraic Geometry

Paul Hriljac · 2025

Read Some NP Complete Problems Based on Algebra and Algebraic Geometry by Paul Hriljac (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-14715.txt.

Introduction

Paul Hriljac presents new hard problems built from algebra and algebraic geometry, in a paper from 2025. Solo work, it links a classic coloring puzzle to deep questions about efficient computation. Coloring graph nodes with elements of a finite field is the bridge.

That coloring step converts coloring problems into membership questions for a new family of varieties tied to determinant varieties. In turn, the famous P versus NP question becomes a question about whether certain high-degree polynomials over finite fields have low multiplicative cost. The paper offers these reframings as fresh angles on a central open problem.

Catalog record

CREATORPaul Hriljac
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-14715

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Some NP Complete Problems Based on Algebra and Algebraic Geometry Paul Hriljac Abstract Notation : Let p be a prime and let \mathbb{F} be a finite field with q=p^{n}\geq 4 elements and algebraic closure \mathbb{\bar{F}} . For sets X,Y let Hom(X,Y) denote the functions from X to Y . For numbers m,n let Hom(m,n) denote Hom(\{1,\dots m\},\{1,\dots,n\}) . Let \Gamma be a connected graph with vertex set V and edge set E . Definition a \mathbb{F} -coloring of \Gamma is an assignment V\rightarrow\mathbb{F^{*}} so that no adjacent vertices share the same value. From now on, suppose that each edge of \Gamma has be given an orientation, so one can speak of the initial vertex and terminal vertex of each edge. Assign to \Gamma the array A_{\Gamma}\in\mathbb{F}^{|V||E|(q-1)} given by A_{\Gamma}(v,e,c)=\begin{cases}&1\text{ if }v=e(0)\\ &c\text{ if }v=e(1)\\ &0\text{ else}.\end{cases} Here v is vertex, e is an edge and c is an element of \mathbb{F}-\{0\} . Let \mathbf{D}_{V,E} be the determintal variety corresponding to |V| by |E| matrices with rank <min(|E|,|V|) (see [3]). We suppress the indices when the context is clear. Then \mathbf{D} is a subscheme of \mathbb{A}^{|V||E|} . For \alpha\in Hom(E,\mathbb{F}-\{0,-1\}) let \pi_{\alpha} be the projection \mathbb{A}^{|V||E|(q-1)}\rightarrow\mathbb{A}^{|V||E|} given by A\mapsto[A(v,e,\alpha(e))]_{v,e} . Let \mathbf{D}_{\alpha}=\pi_{\alpha}^{*}\mathbf{D} and let \mathbf{C}=\mathbf{C}_{|V||E|(q-1)}=\cup_{\alpha}\mathbf{D}_{\alpha} . Call \mathbf{C} the coloring variety associated to graphs with |E| edges, |V| vertices and q-1 colors. Since \mathbf{C} can be defined by cofactor relations, it can be realized as a closed subscheme of \mathbb{A}^{|V||E|(q-1)} . Theorem : Assuming |V|\leq|E| \Gamma is \mathbb{F} - colorable if and only if A_{\Gamma}\in\mathbf{C} . Proof : Given an \mathbb{F} -coloring \{c_{v}\} of \Gamma , Fermat’s Theorem implies c_{v}^{q-1}=1 for all vertices v . Therefore, if v and w are adjacent \frac{c_{v}^{q-1}-c_{w}^{q-1}}{c_{v}-c_{w}}=0. Expanding this out gives \prod_{\alpha\in\mathbb{F}-\{0,-1\}}c_{e(0)}+\alpha c_{e(1)}=0. Therefore c_{e(0)}+\alpha c_{e(1)}=0 for some \alpha=\alpha(e)\in\mathbb{F}-\{0,-1\} , which implies \mathbf{c}M_{\Gamma}=0 where M_{\Gamma}=\pi_{\alpha}(A_{\Gamma})=\begin{cases}&1\text{ if }v=e(0)\\ &\alpha(e)\text{ if }v=e(1)\\ &0\text{ else}\end{cases},\qquad\mathbf{c}=[c_{v}]_{v\in V}. This shows that the rank of \pi_{\alpha}(A_{\Gamma}) is less than |V| and hence A_{\Gamma}\in\mathbf{C} . On the other hand if \pi_{\alpha}(A_{\Gamma}) has rank less than |V| for some \alpha\in Hom(E,\mathbb{F}-\{0,-1\}) than a nonzero vector in the kernel space \pi_{\alpha}(A_{\Gamma}) is easily seen to provide a procedure yielding a valid coloring for the graph. From this proof one sees the Theorem : If |E|<|V| then \Gamma is \mathbb{F} -colorable . Proof : Since |E|<|V| the kernel space of the linear map corresponding to \mathbf{x}\mapsto\mathbf{x}\pi_{\alpha}(A_{\Gamma}) is nonzero for any \alpha . Using a nonzero element of the kernel space one can create a coloring. Example 1 : Try to 3-color the following graph: The theorem implies that the graph has a 3-coloring iff there is a map \alpha:\{1,2,3,4,5\}\rightarrow\mathbb{F}_{4}-\{0,-1\} such that the rank of the matrix \pi_{\alpha}(A_{\Gamma})=\begin{bmatrix}\alpha_{1}&1&0&0&0\\ 0&\alpha_{2}&1&0&\alpha_{5}\\ 1&0&0&\alpha_{4}&1\\ 0&0&\alpha_{3}&1&0\end{bmatrix}. is less than 4. Since the determinant of the matrix with the last column deleted is 1, the rank is never less than 4 so the graph cannot be 3-colored. Definition : Given a family \mathfrak{X}=(X,Y) of varieties X and subvarieities Y\subset X over a field K the membership problem for \mathfrak{X} to be the following: Given P\in X(K) , is P\in Y(K) ? Definition : Let \mathfrak{C}=(\mathbf{C}_{m,n,q-1},\mathbb{A}^{mn(q-1)}) using coloring varities as defined above. Theorem : The membership problem for \mathfrak{C} over a field \mathbb{F} with q\geq 4 elements is NP Complete . Proof : To see that this problem is in NP, one just needs to check the rank of \pi_{\alpha}(A_{\Gamma}) for a given \alpha . To see that this problem is NP hard note that the NP complete problem of \mathbb{F} -coloring graphs is subsumed by this problem. We now introduce another NP complete membership problem with the following example: Example 2 : Consider the graph in Example 1. Parametrize a line in \mathbb{A}^{4,5,2} by \gamma(t)=\begin{bmatrix}\alpha_{1}&t&0&0&1-t\\ 0&\alpha_{2}t&1&0&\alpha_{5}\\ t&0&0&\alpha_{4}&t\\ 0&0&\alpha_{3}&t&0\end{bmatrix}. then \gamma(1)=A_{\Gamma} . Each choice of \alpha yields a 4 by 5 array with coefficients in \mathbb{F}[t] . Taking the five major cofactors of this array gives five polynomials f_{1,\alpha},\dots,f_{5,\alpha} . Taking the greatest common divisor of these polynomials gives a polynomial f_{\alpha} of degree \leq 4 . It is easy to see f_{\alpha}(1)=0\text{ if and only if }\alpha\text{ gives a valid coloring of the graph.} Next suppose \mathcal{F}=\{f(x)_{\alpha}\}_{\alpha\in Hom(n,l)} is a set of polynomials in \mathbb{F}[x] with degree \leq n whose coefficients can be found from \alpha in time polynomial in l,m,n . Let Z(\mathcal{F}) denote the roots of \prod_{\alpha}f_{\alpha} and \mathfrak{Z}=(Z(\mathcal{F}),\mathbb{A}^{1}) . Theorem : The membership problem for \mathfrak{Z} over a field \mathbb{F} with q\geq 4 elements is NP Complete . Proof : Using elementary linear algebra it is easy to check that the variety D_{n,m} is cut out set-theoretically by the equations \delta_{0}=\dots=\delta_{m-n}=0 where \delta_{i} is the determinant of the n\times n matrix consisting of the first n-1 columns of a matrix as well as the column in position n+1 . To decide if some A\in\mathbb{A}^{m,n,l} is in \mathbf{C}_{m,n,l} let L be a line in \mathbb{A}^{m,n,l} parametrized by some linear function \theta(t) with \theta(t_{0})=A . Let f_{\alpha}(t)=gcd[\delta_{0}(\pi_{\alpha}(\theta(t))),\dots,\delta_{m-n}(\pi_{\alpha}(\theta(t)))] . Then A\in\mathbf{D}_{\alpha} iff f_{\alpha}(t_{0})=0 and so A\in\mathbf{C} iff t_{0} is a root of \prod_{\alpha}f_{\alpha} . This shows that the \mathfrak{Z} membership problem is NP-hard. It is easy to see that the problem is in NP: Given \alpha and t_{0} , just check that f_{\alpha}(t_{0})=0 . Definition : A computation tree over a finite field \mathbb{F} is a rooted tree binary with a collection of field elements associated with each node (see [1]). Other than roots and leaves, each node is either a computation or a branch. Each computation node performs an algebraic calculation over that field that depends only on the field elements associated with earlier nodes. The branch nodes have a single associated field element and the two edges emanating from it are labeled "=" and "\neq" . A decision tree T for X\subset\mathbb{F} is a computation tree that decides if some x\in\mathbb{F} belongs in X . The leaves are labeled "\in" and "\notin" . Since the tree is operating only on elements of \mathbb{F} we may assume that the root node has a unique field element. Let |T| denote the length of the longest path through T . Definition : A computation sequence for a polynomial f(x)\in\mathbb{F}[x] is a sequence of polynomials g_{i}(x)\in\mathbb{F}[x],i=0,\dots,r such that: \displaystyle g_{0}=x; \displaystyle g_{i}=(\sum_{j=0}^{i-1}a_{i,j}g_{j})*(\sum_{j=0}^{i-1}b_{i,j}g_{j}),\quad a_{i,j},b_{i,j}\in\mathbb{F}; \displaystyle f(x)=f(0)+\sum_{i=0}^{r}c_{i}*g_{i},\quad c_{i}\in\mathbb{F}; Let \L(f) denote the length of the shortest computation sequence for f . This is the multiplicative complexity of a polynomial f(x)\in\mathbb{F}[x] . Suppose \mathbb{F} is a finite field with q elements and X\subset\mathbb{F} a subset with characteristic function \chi . Then \chi can be realized as a polynomial \chi(x)\in\mathbb{F}[x] . Suppose T is a decision tree for X\subset\mathbb{F} . Then Theorem : L(\chi)\leq 24*log(q)*|T| . To prove the theorem we must introduce some new ideas and discuss their properties. Definition : Given a decision tree for X\subset\mathbb{F} let \mathbf{p}_{x} denote the path T takes when input x\in\mathbb{F} is provided. Let |\mathbf{p}_{x}| denote the total number of internal nodes in \mathbf{p}_{x} . Let \mathbf{p}_{T} be the generic path of T , corresponding to the decision "\neq" at all decision nodes of T . Definition : Say that a decision tree T is pruned if : 1. For every decision node \nu in T there are inputs x,y\in\mathbb{F} such that \mathbf{p}_{x},\mathbf{p}_{y} both pass through \nu but take different forks

Read the complete text