Given a Boolean formula over $n$ variables in CNF and a partial assignment to it, all the algorithms I can think of to evaluate the assignment run in time $\Theta(n^2)$. Is it possible to do it in $O(n)$? I'd say no, because otherwise SAT would be in NTIME(n) and we know that P is different from NTIME(n), but maybe this is a misleading argument.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Also $\mathsf{SAT} \in \mathsf{NTIME}(n)$ would not mean that $\mathsf{NP}\subseteq \mathsf{NTIME}(n)$ because the reductions to a $\mathsf{NP}$-complete problem is polynomial, not necessarily linear. $\endgroup$– NathanielCommented May 30, 2022 at 13:12
-
$\begingroup$ In this case $n$ is the number of variables, I wrote it on the first sentence.As for the other argument, the idea is the following. Suppose that SAT is in NTIME(n) and suppose P = NP. Then NTIME(n) is contained in NP = P, so NTIME(n) is contained in P. Contradiction. So P different from NP. So if there was a way of evaluating CNF formulas in linear time, then we would be able to prove P != NP. $\endgroup$– Noel ArtecheCommented May 30, 2022 at 13:15
-
$\begingroup$ Then again, $\mathsf{SAT}\in\mathsf{NTIME}(n)$ DOES NOT IMPLY $\mathsf{NP}\in\mathsf{NTIME}(n)$. And $\mathsf{NTIME}(n) \subseteq \mathsf{P}$ is not a contradiction if $\mathsf{P} = \mathsf{NP}$. $\endgroup$– NathanielCommented May 30, 2022 at 14:31
-
1$\begingroup$ And it is weird that you want an algorithm to evaluate a formula in time complexity independant of the size of that formula. It is indeed impossible. That was why I was talking about the number of clauses. $\endgroup$– NathanielCommented May 30, 2022 at 14:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No. You can't even do it in $O(n^2)$ time, if $n$ is the number of variables. The formula might be much longer than $\Theta(n^2)$ (it might have many more clauses than that), and obviously any correct algorithm will have to read the entire formula (at least in the worst case), so the running time of any correct algorithm has to be at least as large as the length of the formula. The length of the formula can be as big as $2^n$, so any algorithm to evaluate the formula under a particular assignment might take as long as $O(2^n)$ time, assuming you try to measure its running time only in terms of the number of variables.
In complexity theory, we normally don't measure the running time of algorithms in that way. Typically, we measure the running time as a function of the length of the input, not the number of variables.
