Generare MIN-3-UNSAT $\mathsf{NP}$-è difficile?

Question

Ingresso:quantità di variabili (con un minimo di $ 10 $ poiché altrimenti il ​​problema è irrisolvibile).

Produzione:formula insoddisfacente.

Restrizioni:

1. Ogni clausola contiene esattamente 3 variabili.
2. Ogni clausola differisce per almeno una variabile.Ad esempio, una coppia di clausole $(x\lor y\lor z)\land(x\lor \overline y\lor\overline z)$ è vietata.
3. Ogni variabile deve essere coinvolta.
4. La rimozione di qualsiasi clausola rende la formula soddisfacibile.

Nessun insieme di clausole viene fornito come input.Questo problema è in $\mathsf{FP}$ o è $\mathsf{NP}$-difficile?