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

up vote 10 down vote accepted

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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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