Soddisfazione satellitare con 10 variabili

Question

Sto cercando di dimostrare che il prossimo problema è NPC:

$$ A={\ Langle \ Phi \ Rangle \ \ Big |\ \ phi \ \ text {è cnf e si è seduto.Assegnazione in cui esattamente 10 vars sono true} \} $$

Sto cercando di trovare la riduzione della mappatura polinomiale da Sat ma non riesco a trovare un modo per forzare esattamente 10 variabili per ottenere un vero incarico. La mia idea è stata quella di creare una nuova formula, con 10 clausole, ogni clausola è l'intersezione di una nuova variabile $ x_i $ con la vecchia formula, ma non vedo comeLa mia idea è utile.

apprezzerei l'aiuto.

Answer 1

Il problema che hai menzionato è in $ p $ quindi non è completo.Sappiamo che $ | \ phi |= n $ Quindi il numero di variabili è inferiore a $ N $ e sappiamo che membri di $ a$ avere esattamente 10 tanti incarichi.Quindi da un algoritmo di forza bruta controlla ogni possibile assegnazione alle variabili.Scegli 10 variabili da n, $ (^ {n} _ {10}) $ e impostarli su $ TRUE $ e imposta altre variabili in $ false $ e controlla se questo è un incarico soddisfacente.Il tempo di esecuzione di questo algoritmo è $ (^ {n} _ {10}) * n= o (n ^ {11}) $ .