Находится ли HORN-SAT в LIN, если да, то почему это не означает, что P = LIN?

Зоопарк Сложности определяет как класс задач решения, решаемых детерминированной машиной Тьюринга за линейное время.$LIN$

Поскольку HORN-SAT разрешим в (как указано в алгоритмах линейного времени для проверки выполнимости формул рогового высказывания (1984) )$O(n)$

Представлены новые алгоритмы для определения, является ли (пропозициональная) формула Хорна выполнимой. Если формула Хорна содержит K различных пропозициональных букв, и если предполагается, что они в точности равны P 1 , … , P K , два алгоритма, представленные в этой статье, выполняются за время O ( N ) , где N - общее число вхождений литералов в A .$A$$K$$P_1,…, P_K$$O(N)$$N$$A$

Мне интересно, почему мы не можем сделать вывод, что

учитывая, что HORN-SAT также оказался -завершенным при сокращении пространства журнала ? Я должен что-то упустить. Или это общеизвестный факт?$P$

(Я еще тщательно изучил статью 1984 года, поэтому не совсем понимаю алгоритмы решения задачи HORN-SAT за линейное время, и, следовательно, я, возможно, неправильно понял смысл.)

Поскольку сокращение пространства журнала не обязательно выполняется за линейное время. Если вы возьмете проблему в P и попытаетесь уменьшить ее до HORN-SAT, будет сокращение пространства журнала, но это сокращение может занять больше, чем линейное время. Таким образом, несмотря на то, что HORN-SAT может быть решен за линейное время, другая проблема может быть не решаема за линейное время: вы можете преобразовать его в экземпляр HORN-SAT, а затем решить экземпляр HORN-SAT, но сам процесс преобразования может занять больше, чем линейное время.

$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$$O(n^c)$

$n$

Теорема о детерминированной иерархии времени исключает решение всех задач в P за линейное время. Если вы попытаетесь свести проблему к HORN-SAT, для решения которой требуется больше, чем линейное время, вы обнаружите, что само сокращение требует больше времени, чем линейное.