Zoo Złożoności definiuje jako klasę problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie liniowym.
Ponieważ HORN-SAT można rozwiązać w (jak wskazano w algorytmach czasu liniowego do testowania spełniania formuł róg zdań (1984) )
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
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?
(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).
źródło
Odpowiedzi:
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) n c⋅lgn c b O(2b) 2b c⋅lgn O(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
źródło
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.
źródło