Ist HORN-SAT in LIN, wenn ja, warum ist das kein Hinweis darauf, dass P = LIN ist?

Der Complexity Zoo definiert als die Klasse von Entscheidungsproblemen, die von einer deterministischen Turing-Maschine in linearer Zeit gelöst werden können.$LIN$

Da HORN-SAT in lösbar ist (wie in linearen Zeitalgorithmen zum Testen der Erfüllbarkeit von Aussagenhornformeln angegeben (1984) )$O(n)$

Es werden neue Algorithmen vorgestellt, mit denen entschieden werden kann, ob eine (Satz-) Hornformel erfüllt werden kann. Wenn die Formel Horn enthält K unterschiedliche propositionaler Buchstaben und wenn angenommen wird , dass sie genau P 1 , ... , P K , wobei die beide in diesem Papierlauf vorgestellten Algorithmen in der Zeit O ( N ) , wobei N die Gesamtzahl von Auftritten ist , von Literalen in A .$A$$K$$P_1,…, P_K$$O(N)$$N$$A$

Ich frage mich, warum wir daraus nicht schließen können

in Anbetracht dessen, dass HORN-SAT auch unter logarithmischer Speicherplatzreduzierung als vollständig erwiesen wurde ? Mir muss etwas fehlen. Oder ist das eine bekannte Tatsache?$P$

(Ich habe das Papier von 1984 noch gründlich durchgearbeitet, daher verstehe ich die Algorithmen zum Lösen von HORN-SAT in linearer Zeit nicht ganz und habe daher möglicherweise die Implikation falsch verstanden.)

Weil die Reduzierung des Protokollspeichers nicht unbedingt in linearer Zeit ausgeführt wird. Wenn Sie ein Problem in P nehmen und versuchen, es auf HORN-SAT zu reduzieren, wird der Protokollspeicher reduziert, aber diese Reduzierung kann länger als linear dauern. Obwohl HORN-SAT in linearer Zeit gelöst werden kann, ist das andere Problem möglicherweise nicht in linearer Zeit lösbar: Sie können es in eine HORN-SAT-Instanz konvertieren und dann die HORN-SAT-Instanz lösen, aber der Konvertierungsprozess kann selbst dauern mehr als lineare Zeit.

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

Der deterministische Zeithierarchiesatz schließt aus, dass alle Probleme in P in linearer Zeit entschieden werden. Wenn Sie versuchen, ein Problem auf HORN-SAT zu reduzieren, für dessen Entscheidung mehr als eine lineare Zeit erforderlich ist, werden Sie feststellen, dass die Reduzierung selbst mehr als eine lineare Zeit erfordert.