HORN-SAT está em LIN, se sim, por que isso não é uma indicação de que P = LIN?

O Complexity Zoo define como a classe de problemas de decisão solucionáveis ​​por uma máquina de Turing determinística em tempo linear.$LIN$

Como o HORN-SAT é passível de solução em (conforme indicado nos algoritmos de tempo linear para testar a satisfação das fórmulas de cornetas proposicionais (1984) )$O(n)$

Novos algoritmos para decidir se uma fórmula Horn (proposicional) é satisfatória são apresentados. Se a fórmula Horn contém letras proposicionais distintas e se for assumido que elas são exatamente , os dois algoritmos apresentados neste artigo são executados no tempo , em que é o número total de ocorrências de literais na .$A$$K$$P_1,…, P_K$$O(N)$$N$$A$

Estou me perguntando por que não podemos concluir que

dado que o HORN-SAT também foi comprovado como completo em com redução do espaço de log ? Eu devo estar esquecendo alguma coisa. Ou isso é um fato conhecido?$P$

(Eu ainda analisei completamente o artigo de 1984, então não entendo bem os algoritmos para resolver o HORN-SAT em tempo linear e, portanto, posso ter entendido mal a implicação.)

Porque as reduções do espaço de log não necessariamente são executadas em tempo linear. Se você pegar um problema em P e tentar reduzi-lo para HORN-SAT, haverá uma redução no espaço de log, mas essa redução poderá levar mais que o tempo linear. Portanto, mesmo que o HORN-SAT possa ser resolvido em tempo linear, o outro problema pode não ser solucionável em tempo linear: você pode convertê-lo em uma instância de HORN-SAT e depois resolver a instância de HORN-SAT, mas o processo de conversão pode demorar mais que tempo linear.

Uma redução de espaço de log é aquela em que a quantidade de espaço usada é , em que n é o tamanho da entrada. Em particular, ele pode usar c ⋅ lg n bits de espaço, para alguma constante c . Agora, sabe-se que qualquer algoritmo determinístico que utiliza no máximo b bits de espaço é executado no tempo no máximo O ( 2 b ) [se é garantido que terminará], pois existem apenas 2 b possíveis estados diferentes e se o algoritmo visitar qualquer estado mais de uma vez, ele fará um loop para sempre. Consequentemente, uma redução que usa c $O(\lg n)$$n$$c \cdot \lg n$$c$$b$$O(2^b)$$2^b$ bits de espaço terão tempo de execução no máximo O ( 2 c lg n ) . No entanto, 2 c lg n = ( 2 lg n ) c = n c , então a única conclusão que podemos tirar é que a redução ocorre no tempo O ( n c ) , ou seja, no tempo polinomial.$c \cdot \lg n$$O(2^{c \lg n})$$2^{c \lg n} = (2^{\lg n})^c = n^c$$O(n^c)$

Em outras palavras: uma redução no espaço de log pode levar mais que o tempo linear para ser executada. Seu tempo de execução pode ser qualquer polinômio em .$n$

O teorema da hierarquia determinística do tempo impede que todos os problemas em P sejam decididos em tempo linear. Se você tentar reduzir um problema ao HORN-SAT que exija mais do que tempo linear para decidir, verá que a redução propriamente dita exige mais do que o tempo linear.