Salut,
Cela fait 8 ans que je cherche à résoudre ce problème, sans aucun sucés, néanmoins j'ai réussit à trouver de nouvelle forme de problème NP-complet voilà une liste :
1/Soit
un nombre premier on se place dans le corps à p éléments :
Soit
, existe-t-il
=0)
?
2/Soit
un nombre premier on se place dans le corps à q éléments :
Soit
, le coefficient du monôme de
de degré
vérifie-t-il
?
3/Soit
=\sum_{i=1}^{m} c_i sin(a_i x +b_i) \geq 0)
, existe-t-il
=0)
?
4/Soit une fonction
les composantes de F sont polynomiales de degrés plus petit que
.
a-t-il un point fixe ?
Ordre de grandeur :Si on considère un problème sat-3 classique avec
variable, alors :
=2^{l \times n})
et
avec
.
