# List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem we have a solution then it means the problem has a question. For example we can transform the problem of MAx-Clique to the following set of polynomials

$$P=\{x_i^2-x_i, x\in [n]\}\cup \{x_ix_j, (i,j)\notin E\}$$

I want to know there is any list of problems like this? If you know any paper or book such that there lots of problems like the above one which can transform it to set of polynomials please let me know and have it.

• Every problem in NP can be written like this. For the proof, reduce 1-in-3-SAT to this problem. – Yuval Filmus Feb 7 at 4:20

Suppose that the 3SAT instance has variables $$x_1,\ldots,x_n$$ and clauses $$C_1,\ldots,C_m$$. The new instance will have variables $$x_1,\ldots,x_n,y_1,\ldots,y_m,z_1,\ldots,z_m$$, and the following polynomials:
• $$x_i^2 - x_i$$ for each $$i \in [n]$$ and $$y_j^2 - y_j, z_j^2 - z_j$$ for each $$j \in [m]$$.
• For a clause $$C_\ell$$ of the form $$x_i \lor x_j \lor x_k$$: $$x_i + x_j + x_k - y_\ell - z_\ell - 1$$.
• If a clause has negated variables, say $$x_i$$ appears as $$\overline{x_i}$$, then replace $$x_i$$ with $$1-x_i$$ in the polynomial stated above.
Why does this work, the first type of polynomials constrain all variables to be $$0,1$$. The polynomial $$x_i + x_j + x_k - y_\ell - z_\ell - 1$$ states that $$x_i + x_j + x_k = 1 + y_\ell + z_\ell$$, and since $$y_\ell,z_\ell$$ occur only in this polynomial, this is the same as $$1 \leq x_i + x_j + x_k \leq 3$$, that is, $$x_i + x_j + x_k \geq 1$$, or equivalently, $$x_i \lor x_j \lor x_k$$.