This is based on numerical experiments in sage.
Let $K$ be a ring and define the ideal where each polynomial
is of the form $(a_i x_i+b_i)(a_j x_j+b_j)=0$ for constant $a_i,b_i,a_j,b_j$.
>Q1 Is it true that for constraints of this form the groebner basis is
>efficiently computable?
By "efficiently" we mean polynomial in the number of variables and
wall clock time of seconds for say 100 variables and if we a add
single constraint of other form the running time degrades.
For $K=\mathbb{F}_2$ this is equivalent to 2-SAT, which is
efficiently solvable.
We believe that adding one more linear factor, $(a_k x_k+b_k)$
will be NP-complete.
>Q2 Why adding the factor brings hardness?
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/CAGUWgD95_z_Xt8eZ%2BW1mktQ2ddmX_4HHx%2BwGdBhE8BiUyG7Q%3DQ%40mail.gmail.com.
