Definicje algorytmu działającego w czasie wielomianowym i silnie wielomianowym

Wikipedia to określa

Mówi się, że algorytm ma czas wielomianowy, jeśli jego czas działania jest ograniczony górną granicą przez wyrażenie wielomianowe wielkości wejściowej dla algorytmu, tj. dla pewnej stałej k.$T(n) = O(n^k)$

Algorytm działa w silnie wielomianowym czasie, jeśli [8]

• liczba operacji w modelu arytmetycznym obliczeń jest ograniczona wielomianem w liczbie całkowitej w instancji wejściowej; i

• przestrzeń używana przez algorytm jest ograniczona wielomianem wielkości danych wejściowych.

W Bernhard Korte, Jens Vygen, Optymalizacja kombinatoryczna :

Definicja 1.4.

Algorytm z racjonalnym wejściu mówi się uruchomić w czasie wielomianowym , jeżeli

• istnieje liczba całkowita k, która działa w czasie , gdzie n jest rozmiarem wejściowym, i$O(n^k)$
• wszystkie liczby w obliczeniach pośrednich mogą być przechowywane z bitami .$O(n^k)$

Algorytm z dowolnego wejścia mówi się uruchomić w silnie czasie wielomianowym , jeżeli

• istnieje liczba całkowita k, która działa w czasie dla dowolnego wejścia składającego się z n liczb i$O(n^k)$
• działa w czasie wielomianowym dla racjonalnego wprowadzania danych.

Proszę, popraw mnie jeśli się mylę. Oto dosłowne różnice, które zauważyłem:

• W przypadku algorytmów wielomianowych definicja Korte i Vygen'a to „definicja Wikipedii + wielomianowe miejsce do przechowywania”.

• W przypadku algorytmów silnie wielomianowych zarówno definicja Korte i Vygen, jak i definicja Wikipedii wymagają czasu wielomianowego w wielkości wejściowej pamięci. Ale K i V dodatkowo wymagają wielomianowego czasu w liczbie liczb na dowolnym wejściu, podczas gdy Wikipedia dodatkowo wymaga wielomianowego miejsca do przechowywania w wielkości wejściowej.

Czy zatem definicje K, V i Wikipedii dla tych dwóch pojęć są odpowiednio równoważne? Jakie są inne różnice i relacje między nimi?

Dziękuję i pozdrawiam!

Przed formalnymi definicjami zastanów się, co wyróżnia klasyfikacja „silna / słaba”.

Najpierw rozważ uruchomienie jednego z nich na maszynie Turinga. Oba będą działać w kilku krokach wielomianowych o długości wejścia kodowanego binarnie. W związku z tym liczba operacji arytmetycznych wykonywanych przez oba musiałaby być wielomianowa w długości wejścia kodowanego binarnie . Dlatego dla obu maszyn Turinga czas działania wzrastałby wielomianowo wraz ze wzrostem liczby wartości wejściowych lub ich wielkości. Aby podkreślić to drugie, zauważ, że nawet mocny wykona więcej kroków TM na większych wielkościach (musi przynajmniej odczytać dodatkowe bity). W żadnym wypadku nie staje się wykładniczy (jak ma to miejsce w przypadku niepowiązanego czasu pseudo-wielomianu). W przypadku samej maszyny Turinga zasadnicza różnica nie wydaje się wykrywalna.

$O(1)$

Zbiór algorytmów, które działają wielomianowo w liczbie operacji arytmetycznych pod względem liczby liczb wejściowych, jest dobrze zdefiniowany, ale nakłada się na klasę algorytmów, które przyjmują wykładniczą liczbę kroków TM w długości wejścia kodowanego binarnie (patrz przykłady ). W związku z tym dla tego zestawu właściwości w drugim akapicie nie zostałyby zachowane. Aby wykluczyć niechciane przecięcie, dodajemy warunek dla wielomianowej przestrzeni TM [*].

W [1] jest to stwierdzone na dwa sposoby:

• Algorytm działa w silnie wielomianowym czasie, jeśli algorytm jest algorytmem przestrzeni wielomianowej i wykonuje szereg elementarnych operacji arytmetycznych, które są ograniczone przez wielomian w liczbie liczb wejściowych.
• Algorytm wielomianowy to algorytm wielomianowej przestrzeni (w naszym standardowym modelu maszyny Turinga) i wielomianowy algorytm czasowy w modelu arytmetycznym ( wyjaśnienie znajduje się w tym pytaniu ).

$O(n^3)$$O(n^2)$

[*] Drugi warunek jest określany wszędzie jako przestrzeń wielomianowa, podczas gdy wymaganie czasu wielomianowego ma dla mnie większy sens. Ten pierwszy jest bardziej integracyjny, ale dziwny. Czy istnieją algorytmy silnie wielomianowe, które zajmują więcej niż czas wielomianowy? Zauważ, że przykład wielokrotnego kwadratowania nie bierze ani czasu wielomianu, ani przestrzeni wielomianowej.

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). „Złożoność, wyrocznie i obliczenia numeryczne”. Algorytmy geometryczne i optymalizacja kombinatoryczna. Skoczek. ISBN 0-387-13624-X.