Complessità a grana fine della valutazione della formula 3-CNF

Question

È noto che 3-Sat è in NP, il che significa che si può valutare una formula 3-CNF nel tempo polinomiale. Tuttavia, mi chiedevo quale fosse il limite superiore più stretto per la verifica della formula, espressa in notazione Big-O o in qualche altro modo.

La mia ipotesi migliore è che le formule 3-CNF possano essere verificate in tempo lineare nel numero di clausole. Ogni clausola ha due disgiunzioni e fino a tre negazioni, che dovrebbero richiedere un passo per valutare. Se si conta in sostituzione di un letterale con il suo valore assegnato come passo, ciò ti dà al massimo 8 passaggi per clausola. Quindi, una volta valutate tutte le clausole, è necessario [# di clausole] - 1 passaggi per calcolare tutte le congiunzioni tra loro. Quindi con $ x $ clausole, questo è al massimo $ 8x + x - 1 = 9x - 1 $ Passi in totale, che è $ O (x) $.

Ovviamente, se mi sbaglio, per favore fammelo sapere, e se ci sono anche limiti di tempo migliori (teorici o pratici), mi piacerebbe conoscerlo anche su quelli.