2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ See also cstheory.stackexchange.com/questions/18756/…. $\endgroup$
    – GManNickG
    May 30, 2022 at 19:02
  • 1
    $\begingroup$ Remember that the complexity class NP is defined in terms of Turing machines. The input size is the number of symbols on the tape. $\endgroup$
    – Pseudonym
    May 31, 2022 at 0:47

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The input is just a Boolean formula $\phi$.

$|\phi|$ depends on the way in which $\phi$ has been encoded.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.