Boolean SAT problem (NP-complete)

Question

I’m trying to get my head around exactly what this problem is asking. The part I’m struggling with is how we measure complexity of the problem.

Would $(a\implies b)$ be regarded as less complicated than $(a \wedge b) \vee (a \implies b)$

Is the complexity measured by the number of logical operations or by the number of variables in the expression or by the number of different variables or by the number of symbols?

Thanks in advance, Ben

Answer 1

There are different ways of measuring the size of a problem, but essentially it is the number of bits used to express it. So yes, $(a \implies b)$ would be smaller than $(a \wedge b) \vee (a \implies b)$ (even though they turn out to be logically equivalent).