Problemy, które prawdopodobnie wymagają czasu kwadratowego

Szukam przykładów problemu, który ma dolną granicę ) dla wejścia . $\Omega(|x|^2$ $x$

Problem musi mieć następujące właściwości:

$\Omega(n^2)$ Środowisko wykonawcze dla dowolnego algorytmu - priorytetem jest możliwie najprostszy argument dolnej granicy.
$O(n^2)$ Algorytm , jeśli to możliwe, również prosty.
Rozmiar wyjściowy (lub mniejszy). Oczywiście każdy problem, który wymaga wydłużonego wyjścia wymagał co najmniej podobnego czasu działania, ale nie tego szukam. Zauważ, że każdy problem decyzyjny pasuje tutaj. $O(n)$ $\Omega(n^2)$
(jeśli to możliwe) problem „naturalny”. Bez formalnej definicji preferowany jest problem, który rozpoznałby każdy absolwent CS.

Ostatnio zapytano mnie o taki problem, ale nie mogłem wymyślić prostego. Pierwszym problemem, który przyszedł mi do głowy, było , które zostało skonstruowane jako problem czasu wykonywania . Nie było to dość proste, a co więcej, niedawno udowodniono , że koniugacja jest nieprawdziwa : o. $3SUM$ $\Omega(n^2)$

Przechodząc do niezwykle nienaturalnego problemu, uważam, że problem, który pobiera jako dane wejściowe deterministyczną TM i wprowadza , i wyświetla pozycję głowicy taśmy po kroki, gdy działa na prawdopodobnie odpowiada na pytanie. $\langle M \rangle,x$ $(|M|+|x|)^2$ $x$

Jeśli jest to absolutnie konieczne, zgódźmy się, że używamy modelu TM z pojedynczą taśmą, chociaż wolę problemy, których środowisko wykonawcze jest niezależne od dokładnego modelu (o ile jest to uzasadnione).

Czy możemy zatem znaleźć prosty (do udowodnienia), naturalny (dobrze znany) problem, którego środowiskiem wykonawczym jest ? $\Theta(n^2)$

Myślę, że „Biorąc pod uwagę liczby naturalne

, oblicz ” kwalifikuje się. Zwróć też uwagę na to pytanie .

x

$x$

y

$y$

x + y

$x+y$

Raphael

Jedynym sposobem, w jaki wiemy, jak udowodnić superliniowe dolne granice na wielopasmowych maszynach Turinga, jest przekątna. W przypadku maszyn Turinga z pojedynczą taśmą można uzyskać nieco lepsze wyniki, stosując sekwencje krzyżujące, ale nie do

chyba że ograniczysz przestrzeń.

n^{2}

$n^2$

Yuval Filmus

Zobacz tutaj inne powiązane pytanie; odwrócenie wejścia wydaje się być dobrym kandydatem.

Raphael

Nie sądzę, że można to zrobić z problemem decyzyjnym, ponieważ najlepiej znalezioną dolną granicą NP jest O (n).

Albert Hendriks,

Dzięki za komentarz @AlbertHendriks. Czy możesz podzielić się odniesieniem do źródła / ankiety, w którym twierdzi się, że najbardziej znaną dolną granicą dowolnego problemu w NP jest

Ω (n)

$\Omega(n)$

Odpowiedzi:

Znalezienie wolnego od zazdrości cięcia ciasta wymaga kwerend . Nie odpowiada to jednak bezpośrednio na twoje pytanie, ponieważ model obliczeniowy jest inny niż maszyna Turinga. $\Omega(n^2)$

Nawiasem mówiąc, obecnie najszybszy znany algorytm dla tego problemu wymaga zapytań, więc istnieje ogromna luka od dolnej granicy - prawdopodobnie jedna z największych luk w informatyce. $n^{n^{n^{n^{n^{n}}}}}$

Erel Segal-Halevi
źródło

Podobnie jak w linku dostarczonym przez Raphaela, Peter pokazuje, że Odwrócenie Input wymaga $\Theta(n^2)$ czasu na waniliowych TM z pojedynczą taśmą. W przypadku problemu decyzyjnego język

L = {x 0^{| x |} x ∣ x \in {0, 1}^{*}}

$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$ również z pewnością potrzebuje

Θ (n^{2})

$\Theta(n^2)$ czasu na obliczenia. Aby to zobaczyć, skorzystaj z argumentu złożoności komunikacji Piotra wraz z klasycznym wynikiem, którego potrzebuje

E Q_{n}

$EQ_n$

Θ (n)

$\Theta(n)$ bitów komunikacji, aby pokazać kwadratową dolną granicę

L

$L$ Podobne podejście działa dla bardziej naturalnego

L = {x x ∣ x \in {0, 1}^{*}}

$L = \{xx \mid x \in \{0,1\}^\ast \}$ .

Nawiasem mówiąc, warto wspomnieć, że wspomniana przez Yuvala „metoda przekraczania sekwencji” jest (według mojej najlepszej wiedzy) matematycznie równoważna (a może nawet gorsza) od złożoności komunikacyjnej.

$\mathsf{SAT}$ $O(n^{2 \cos(\pi/7)})$ $n^{o(1)}$ $2 \cos(\pi/7) \approx 1.8$

Lwiny
źródło