The decision problem CNF-SAT can be described as follows:Input: A boolean formula $\phi$ in conjunctive normal form.Question: Does there exist a variable assignment that satisfies $\phi$?I'm considering several different approaches for solving CNF-SAT with a non-deterministic two-tape Turing machine.I believe that there is an NTM that solves CNF-SAT in $n \cdot \texttt{poly}(\log(n))$ steps.Question: Is there an NTM that solves CNF-SAT in $O(n)$ steps?Any relevant references are appreciated even if they only provide near linear time non-deterministic approaches.
Is there a non-deterministic linear time algorithm for CNF-SAT?
time complexity;sat;turing machines;np;nondeterminism