Timeline for Time-complexity of evaluating a CNF formula
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 29, 2022 at 19:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 30, 2022 at 18:02 | answer | added | D.W.♦ | timeline score: 1 | |
| May 30, 2022 at 14:32 | comment | added | Nathaniel | 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. | |
| May 30, 2022 at 14:31 | comment | added | Nathaniel | 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}$. | |
| May 30, 2022 at 13:15 | comment | added | Noel Arteche | 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. | |
| May 30, 2022 at 13:12 | comment | added | Nathaniel | 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. | |
| May 30, 2022 at 13:04 | history | asked | Noel Arteche | CC BY-SA 4.0 |