Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

Question

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.)

Answer 1

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$.

Answer 2

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.