Complexité à grains fins de l'évaluation des formules de 3-CNF

Question

Il est bien connu que le 3-SAT est en NP, ce qui signifie que l'on peut évaluer une formule 3-CNF en temps polynomial. Cependant, je me demandais quelle est la limite supérieure la plus serrée pour la vérification des formules, exprimée en notation Big-O ou d'une autre manière.

Ma meilleure supposition est que les formules de 3-CNF peuvent être vérifiées en temps linéaire dans le nombre de clauses. Chaque clause a deux disjonctions et jusqu'à trois négations, ce qui devrait chacune nécessiter une étape pour évaluer. Si vous comptez remplacer un littéral par sa valeur attribuée en tant qu'étape, cela vous donne au plus 8 étapes par clause. Ensuite, une fois que toutes les clauses sont évaluées, vous devez avoir besoin de [# des clauses] - 1 étapes pour calculer toutes les conjonctions entre elles. Donc avec $ x $ clauses, c'est tout au plus 8 x + x - 1 = 9x - 1 $ étapes totales, qui est $ O (x) $.

De toute évidence, si je me trompe à ce sujet, faites-le moi savoir, et s'il y a encore de meilleures limites de temps (théoriques ou pratiques), j'aimerais également en savoir plus.