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

11

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

LINP

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 AAKP1,,PKO(N)NA

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

LIN=P

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).

V 奇 说 ArchVlog - 何魏奇
źródło
3
Nie jest jasne, czy HORN-SAT można rozwiązać w czasie na maszynie Turinga; zwykły algorytm działa w modelu maszyny RAM. O(n)
Yuval Filmus,
2
Ściśle powiązane: cs.stackexchange.com/q/45007/9550
David Richerby,

Odpowiedzi:

10

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(lgn)nclgncbO(2b)2bclgnO(2clgn)2clgn=(2lgn)c=nc , więc jedynym wnioskiem, jaki możemy wyciągnąć, jest to, że redukcja przebiega w czasie , tj. W wielomianu czas.O(nc)

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

DW
źródło
11

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.

Kyle Jones
źródło