Czy HORN-SAT w LIN, jeśli tak, to dlaczego nie oznacza to, że P = LIN?

Zoo Złożoności definiuje jako klasę problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie liniowym.$LIN$

Ponieważ HORN-SAT można rozwiązać w (jak wskazano w algorytmach czasu liniowego do testowania spełniania formuł róg zdań (1984) )$O(n)$

Przedstawiono nowe algorytmy decydujące o tym, czy formuła (zdania) Horn jest zadowalająca. Jeśli wzór Horn zawiera różnych liter zdań i jeśli założymy, że są to dokładnie , dwa algorytmy przedstawione w tym artykule działają w czasie , gdzie jest całkowitą liczbą wystąpień literałów w .K P 1 , … , P K O ( N ) N $A$$K$$P_1,…, P_K$$O(N)$$N$$A$

Zastanawiam się, dlaczego nie możemy tego wyciągnąć

biorąc pod uwagę, że HORN-SAT również okazał się być kompletny przy redukcji przestrzeni logów ? Coś mi brakuje. Czy jest to dobrze znany fakt?$P$

(Jeszcze dokładnie zapoznałem się z artykułem z 1984 r., Więc nie do końca rozumiem algorytmy rozwiązywania HORN-SAT w czasie liniowym, a zatem mogłem źle zrozumieć konsekwencje).

Ponieważ redukcje przestrzeni logicznej niekoniecznie muszą przebiegać w czasie liniowym. Jeśli weźmiesz problem z P i spróbujesz go zredukować do HORN-SAT, nastąpi zmniejszenie przestrzeni logów, ale redukcja ta może zająć więcej niż czas liniowy. Dlatego nawet jeśli HORN-SAT można rozwiązać w czasie liniowym, inny problem może nie być rozwiązany w czasie liniowym: możesz przekonwertować go na instancję HORN-SAT, a następnie rozwiązać instancję HORN-SAT, ale sam proces konwersji może zająć więcej niż czas liniowy.

Zmniejszenie przestrzeni dziennika to takie, w którym ilość wykorzystanego miejsca wynosi , gdzie jest rozmiarem wejściowym. W szczególności może używać bitów przestrzeni, dla niektórych stałych . Obecnie nie wiadomo, że każdy algorytm deterministyczny które zastosowania w większości bitów tras przestrzeni czasu, w większości [jeśli jest to zagwarantowane, aby zakończyć], gdyż istnieje tylko możliwe różne stany, a jeśli wizyt algorytmu w dowolnym stanie więcej niż jeden raz zapętli się na zawsze. W związku z tym redukcja wykorzystująca bitów miejsca będzie miała czas działania co najwyżej . Jednak,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$ , więc jedynym wnioskiem, jaki możemy wyciągnąć, jest to, że redukcja przebiega w czasie , tj. W wielomianu czas.$O(n^c)$

Innymi słowy: zmniejszenie przestrzeni logów może zająć więcej niż czas liniowy. Jego czas działania może być dowolnym wielomianem w .$n$

Twierdzenie o deterministycznej hierarchii czasu wyklucza rozstrzyganie wszystkich problemów w P w czasie liniowym. Jeśli spróbujesz zredukować problem do HORN-SAT, który wymaga więcej niż czasu liniowego do podjęcia decyzji, okaże się, że sama redukcja wymaga więcej niż czasu liniowego.