La génération de min-3-unsat $ mathsf {np} $ - dur?

Question

Entrée: montant des variables (avec un minimum de 10 $, car le problème autrement est insoluble).

Sortie: formule insatisfaisante.

Restrictions:

1. Chaque clause contient exactement 3 variables.
2. Chaque clause diffère d'au moins une variable. Par exemple, une paire de clauses $ (x lor y lor z) land (x lor overline y lor overline z) $ est interdite.
3. Chaque variable doit être impliquée.
4. La suppression de toute clause rend la formule satisfaisante.

Aucun ensemble de clauses n'est donné en entrée. Ce problème est-il dans $ mathsf {fp} $ ou est-ce $ mathsf {np} $ - dur?