All Questions
Tagged with sat nt.number-theory
3 questions
1
vote
1
answer
83
views
Complexity of solving system of binary quadratic equations modulo $3$
A special case of this question and
another question
What is the complexity of solving system of binary quadratic equations modulo
$3$?
$f_i(x_i,x_j)=0 \bmod 3, \deg{f_i}=2$.
Modulo $2$ can be ...
1
vote
0
answers
78
views
On binary constraints defined by vanishing of bivariate polynomials modulo $n$ [duplicate]
In an answer here
Dima Pasechnik showed that constraints of the form $x_i x_j + a_{ij}x_i + b_{ij}x_j + c_{ij}$ are efficiently solvable modulo $2$ using Groebner basis.
In comments he suggested that ...
2
votes
1
answer
130
views
Efficiency of Groebner basis for constraints of the form $(a_i x_i+b_i)(a_j x_j+b_j)$
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)$ for constant $a_i,b_i,a_j,b_j$.
Q1 Is it true ...