# what does **input** mean for the $3SAT$ question? Is it the number of variables $n$ or the number of clauses $m$

We know that $$3SAT \in NP$$, and the definition of $$NP$$ is as follows:

$$NP$$ is the class of languages that have polynomial time verifiers.

But I have a question:

what does input mean for the $$3SAT$$ question? Is it the number of variables $$n$$ or the number of clauses $$m$$,

Let's take an example, given a CNF expression, whose clauses has exactly 3 literals. The CNF expression consists of $$m$$ clauses involving $$n$$ variables $$x_1, ..., x_n$$.

If the input refers to the number of variables $$n$$, and the Boolean formula has $$2^n$$ clauses, it is obvious that an assignment of the validation formula requires $$3*2^n$$ steps, not polynomial time.This contradicts that $$3SAT \in NP$$

If the input refers to the number of clauses $$m$$, an assignment of the validation formula requires 3*m steps, which is polynomial time, which makes sense

So I think for the 3sat problem, the input refers to the number of clauses $$m$$, Is there a problem with my idea？

• May 30, 2022 at 19:02
• Remember that the complexity class NP is defined in terms of Turing machines. The input size is the number of symbols on the tape. May 31, 2022 at 0:47

Neither. The input is the Boolean formula $$\phi$$. You are probably asking what is the length of the input, as computational complexity tries to express the running time of the algorithm as a function of the length of the input. The length of $$\phi$$ depends on how it is encoded, but typically the length will depend on both $$n$$ and $$m$$. A reasonable estimate, for a typical encoding, is $$\Theta(m \log n)$$. If you want to think of the length of the input as $$m$$ that is a plausible approximation that is likely to be good enough for many purposes. As long as you use a reasonable encoding, the exact details are unlikely to change whether an algorithm is polynomial-time or not.
The input is just a Boolean formula $$\phi$$.
$$|\phi|$$ depends on the way in which $$\phi$$ has been encoded.