Déterminez si un système de $ n $ équations linéaires a des solutions dans $ {0, 1 } ^ n $ en temps polynomial

Question

J'essaie de déterminer s'il est possible de décider si un système de $ n $ équations linéaires avec des coefficients entiers et $ n $ Les variables ont une solution dans $ {0, 1 } ^ n $ en temps polynomial.

De plus, tous les coefficients de $ A $ sont dans $\{-1, 0, 1\}$, mais je n'ai pas pu trouver un moyen de l'utiliser.

Le cas trivial est si la (matrice $ A $ du) système est inversible, il n'y a qu'une seule solution, il est facile de vérifier si tous appartiennent $\{0,1\}$.

Cependant, si vous avez une infinité de solutions, et $ k $ variable gratuite, je ne trouve pas de moyen de faire mieux que de vérifier tous les 2 $ ^ k $ possibilités.

• Connaissez-vous un algorithme pour le faire en temps polynomial?

J'ai également essayé de faire une réduction par rapport à SAT (ou une variante avec n clauses et n variables dans chaque clause, pour montrer qu'il est complet NP), mais à cause du fait que nous avons $ Ax = b $ et pas $ Ax geq b $, Je ne pouvais pas faire ça non plus.

• Avez-vous une réduction pour montrer que ce problème est terminé NP?