The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time.

$$LIN \subseteq P$$

Since HORN-SAT is solvable in $O(n)$ (as indicated in Linear-time algorithms for testing the satisfiability of propositional horn formulae (1984))

New algorithms for deciding whether a (propositional) Horn formula is satisfiable are presented. If the Horn formula $A$ contains $K$ distinct propositional letters and if it is assumed that they are exactly $P_1,…, P_K$, the two algorithms presented in this paper run in time $O(N)$, where $N$ is the total number of occurrences of literals in $A$.

I am wondering why we can't conclude that

$$LIN = P$$

given that HORN-SAT has also been proven to be $P$-complete under log-space reduction? I must be missing something. Or is that a well-known fact?

(I have yet thoroughly gone through the 1984 paper so I don't quite understand the algorithms for solving HORN-SAT in linear time, and thus I may have misunderstood the implication.)

  • 3
    $\begingroup$ It's not clear that HORN-SAT is solvable in time $O(n)$ on a Turing machine; the usual algorithm runs in the RAM machine model. $\endgroup$ Commented Aug 5, 2015 at 19:21
  • 2
    $\begingroup$ Closely related: cs.stackexchange.com/q/45007/9550 $\endgroup$ Commented Aug 5, 2015 at 21:07

2 Answers 2


Because log-space reductions don't necessarily run in linear time. If you take a problem in P and try to reduce it to HORN-SAT, there will be a log-space reduction, but that reduction might take more than linear time. Thus even though HORN-SAT can be solved in linear time, the other problem might not be solvable in linear time: you can convert it into a HORN-SAT instance and then solve the HORN-SAT instance, but the conversion process might itself take more than linear time.

A log-space reduction is one where the amount of space used is $O(\lg n)$, where $n$ is the input size. In particular, it might use $c \cdot \lg n$ bits of space, for some constant $c$. Now it's known that any deterministic algorithm which uses at most $b$ bits of space runs in time at most $O(2^b)$ [if it's guaranteed to terminate], as there are only $2^b$ possible different states, and if the algorithm visits any state more than once, it will loop forever. Consequently, a reduction that uses $c \cdot \lg n$ bits of space will have running time at most $O(2^{c \lg n})$. However, $2^{c \lg n} = (2^{\lg n})^c = n^c$, so the only conclusion we can draw is that the reduction runs in $O(n^c)$ time, i.e., in polynomial time.

In other words: a log-space reduction can take more than linear time to execute. Its running time can be any polynomial in $n$.


The deterministic time hierarchy theorem precludes all problems in P being decided in linear time. If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll find that the reduction itself requires more than linear time.


Your Answer

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

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