On 31 January 2024 16:42:39 GMT, Georgi Guninski <ggunin...@gmail.com> wrote:
>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$.
Do you have exactly one (or at most) relation for any pair of variables? Can
one have i=j ?
Or it's the notation which should be improved?
>
>>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/A526B762-E079-45B2-825A-76DF9490C499%40gmail.com.
