¿Está HORN-SAT en LIN? Si es así, ¿por qué no es una indicación de que P = LIN?

Complexity Zoo define como la clase de problemas de decisión que puede resolver una máquina de Turing determinista en tiempo lineal.$LIN$

Dado que HORN-SAT se puede resolver en (como se indica en los algoritmos de tiempo lineal para probar la satisfabilidad de las fórmulas proposicionales de bocina (1984) )$O(n)$

Se presentan nuevos algoritmos para decidir si una fórmula de Horn (proposicional) es satisfactoria. Si la fórmula Horn contiene letras proposicionales distintas y si se supone que son exactamente , los dos algoritmos presentados en este artículo se ejecutan en el tiempo , donde es el número total de ocurrencias de literales en .$A$$K$$P_1,…, P_K$$O(N)$$N$$A$

Me pregunto por qué no podemos concluir que

dado que HORN-SAT también ha demostrado ser completo bajo reducción de espacio logarítmico ? Debo estar perdiendo algo. ¿O es un hecho bien conocido?$P$

(Todavía he revisado minuciosamente el artículo de 1984, por lo que no entiendo los algoritmos para resolver HORN-SAT en tiempo lineal y, por lo tanto, es posible que haya entendido mal la implicación).

Porque las reducciones de espacio logarítmico no necesariamente se ejecutan en tiempo lineal. Si toma un problema en P e intenta reducirlo a HORN-SAT, habrá una reducción del espacio logarítmico, pero esa reducción puede llevar más tiempo lineal. Por lo tanto, aunque HORN-SAT puede resolverse en tiempo lineal, el otro problema podría no resolverse en tiempo lineal: puede convertirlo en una instancia de HORN-SAT y luego resolver la instancia de HORN-SAT, pero el proceso de conversión podría tomar Más que el tiempo lineal.

Una reducción de espacio logarítmico es aquella en la que la cantidad de espacio utilizado es , donde es el tamaño de entrada. En particular, podría usar bits de espacio, para alguna constante . Ahora se sabe que cualquier algoritmo determinista que utiliza a lo sumo bits de espacio se ejecuta en el tiempo a lo sumo [si se garantiza que termine], ya que solo hay posibles estados diferentes, y si el algoritmo visita cualquier estado más de una vez, se repetirá para siempre. En consecuencia, una reducción que use bits de espacio tendrá un tiempo de ejecución como máximo . Sin embargo,n c ⋅ lg n c b O ( 2 b ) 2 b c ⋅ lg n O ( 2 c lg n ) 2 c lg n = ( 2 lg n ) c = n c O ( n c$O(\lg n)$$n$$c \cdot \lg n$$c$$b$$O(2^b)$$2^b$$c \cdot \lg n$$O(2^{c \lg n})$$2^{c \lg n} = (2^{\lg n})^c = n^c$ , por lo que la única conclusión que podemos sacar es que la reducción se ejecuta en tiempo , es decir, en polinomio hora.$O(n^c)$

En otras palabras: una reducción del espacio logarítmico puede tomar más tiempo lineal que ejecutarse. Su tiempo de ejecución puede ser cualquier polinomio en .$n$

El teorema determinista de la jerarquía temporal excluye que todos los problemas en P se decidan en tiempo lineal. Si intenta reducir un problema a HORN-SAT que requiere más que un tiempo lineal para decidir, encontrará que la reducción en sí misma requiere más que un tiempo lineal.