Prova che positivo-3-sat è nella classe complessima p

Question

Ho la seguente lingua:

$$ text {positivo-3-sat} = { langle phi rangle mid phi text {è una formula booleana soddisfacente in forma normale congiuntiva,} text {in cui tutte le clausole consistono esattamente in 3 letterali e in cui nessuna variabile appare negata} }. $$

---

Progressi finora:

La mia preoccupazione è che non ho capito il compito. Ho proposto quella che penso sia una prova (quasi banale).

Per dimostrare che la lingua è in P, Il mio approccio è fornire un algoritmo deterministico che può decidere il problema nel tempo polinomiale.

Per definizione, $ text {positivo-3-sat} $ deve comprendere un numero arbitrariamente lungo di congiunzioni di clausole della forma $ ( lambda_1 lor lambda_2 lor lambda_3) $. Ogni clausola è banalmente soddisfacente nel caso in cui un valore di verità di true sia assegnato a una qualsiasi delle clausole $ lambda_1, lambda_2, lambda_3 $. Su questa base, ogni clausola contenente 3 letterali può essere decisa $ O (3) $ Passi, $ equiv o (1) $.

Se presumiamo il presupposto che il linguaggio sia costretto a contenere solo un numero finito di $ n $ clausole, quindi possiamo dire che la soddisfazione della lingua può essere decisa $ O (n) equiv o (n^1) $ Passi.

Così, $ text {positivo-3-sat} $ può essere deciso da un algoritmo deterministico nel tempo polinomiale.

Così, $ text {positivo-3-sat} in $ Np.