Let be a propositional formula and T a truth assignment for the variables of . Then the function gives the score of T for . Let be a propositional formula and T a truth assignment for the variables of . Then the number of operations required for calculating grows linearly with the size of . It follows from Sections , that we can extend GSAT to non-clausal formulas by simply using the extended notion of score of Definition .
Theorem ensures that every score computation is performed in linear time.
This allows a strong reduction in computational cost. The latter mirrors the complexity issues presented in Section . All these variants, proposed in , can be transposed into NC-GSAT as well, as they are independent of the structure of the input formula. This is independent of the form of the input formula. One final observation is worth making.