Możliwe do przewidzenia luki między złożonością drzewa decyzyjnego a „prawdziwą” złożonością

Tytuł jest trochę mylący: ale mam nadzieję, że pytanie nie brzmi:

Grønlund and Pettie Nowa wynik pokazujący, że 3SUM ma tylko drzewo decyzyjne złożoność got me zastanawiasz się: $O(n^{3/2})$

Czy istnieje prosty przykład problemu ze złożonością drzewa decyzyjnego ale który dopuszcza dolną granicę (w bardziej szczegółowym modelu) ? $O(f)$ $\omega(f)$

Innymi słowy, w jaki sposób wynik na 3SUM powinien zmienić nasze spojrzenie na możliwość uzyskania znacznie niższej niż górnej granicy złożoności problemu? $n^2$

cc.complexity-theory machine-models decision-trees

— Suresh Venkat
źródło

Wyróżnienie elementu można rozwiązać za pomocą binarnego drzewa decyzyjnego o stałej głębokości. („Czy wszystkie elementy są różne?”) Ale potrzebujemy głębokości

aby rozwiązać problem za pomocą liniowych drzew decyzyjnych.

Ω (n \log n)

$\Omega(n\log n)$

— Jeffε

Model drzewa decyzyjnego jest modelem teoretycznym informacji: gdy nauczysz się wystarczająco dużo informacji na temat swojego wkładu, że odpowiedź jest jednoznacznie określona na podstawie tych informacji, jesteś gotowy. Nie ma znaczenia, czy określenie odpowiedzi na podstawie tych informacji jest nierozstrzygalne. Na przykład, jeśli dane wejściowe to n-bitowy ciąg binarny kodujący maszynę Turinga, a pytanie brzmi, czy ta TM zatrzymuje się, drzewo decyzyjne głębokości n może trywialnie rozwiązać ten problem, ponieważ zna wszystkie n bitów, ale żaden algorytm nie może rozwiązać ten problem.

— Robin Kothari,

Może powinienem zamiast tego powiedzieć „przykład prostego problemu” :).

— Suresh Venkat

Odpowiedzi:

$O(n^4\log n)$

— Jeffε
źródło

Gdybym chciał być NAPRAWDĘ PEDANTYCZNY, wskazałbym, że bycie twardym na NP nie jest twardą dolną granicą. ale to dobry przykład ducha tego, czego szukam.

— Suresh Venkat

Tak, ale nie wiemy, jak udowodnić mocne dolne granice.

— Jeffε

@ Jɛ ﬀ E Być może znasz miły opis lub prezentację tego wyniku? Uważam, że oryginał jest bardzo trudny do naśladowania, niektóre definicje wcale nie są dla mnie jasne.

— domotorp

Przynajmniej podstawowe definicje są opisane w moim artykule na temat problemów zwyrodnienia liniowego .

— Jeffε

$O(n\log(\frac{m+n}{n}))$ $\Theta(n+m)$ $m=\omega(n)$

— Seth Pettie
źródło

Pozwól mi trochę się nie zgodzić. W modelu RAM niekoniecznie musimy czytać całe dane wejściowe. W modelu maszyny Turinga istnieje wiele trywialnych problemów, które można rozwiązać szybciej za pomocą drzewa decyzyjnego (lub na maszynie RAM). Zobacz także komentarz Robina do pierwotnego pytania.

— domotorp