Tudtok olyan algoritmust, ami théta szuper-logaritmus n idő alatt fut le?

A théta szuper-logaritmus egy olyan függvény, amely nagyon lassan növekszik, gyakorlatilag lassabban, mint a logaritmus. Az algoritmusok hatékonyságát általában a bemenet mérete határozza meg, és ha az algoritmus futási ideje nagyobb, mint a bemenet mérete az exponenciális növekedésre utal. Azonban vannak olyan algoritmusok, amelyek képesek lefuttatni bizonyos problémákat a théta szuper-logaritmuson belül.

Egy ilyen algoritmus például az ún. quantum walk algoritmus, amely kvantumszámítógépek segítségével működik. A quantum walk algoritmus képes a szimmetrikus csoportok, például a permutáció csoportok inverziós számának meghatározására, ami nagyon fontos a számítástudományban és a matematikában. Az algoritmus futási ideje azonban n^2 log n, ami jobb, mint az exponenciális futási idő, de még mindig nagyobb, mint a théta szuper-logaritmus.

Talán nincsen ilyen algoritmus, egyébként. Se még gyorsabb (de nem O(1)).

Eleve, jó lenne, ha beolvasnánk az inputot, ami log(n) idő. De mondjuk olyan algoritmus sincsen, ami akár sokáig is futhat (beolvassa az inputot), de mondjuk kevés (de nem korlátos) tárhelyet haszál fel.

Megmutatható hogy egy 1-irányú Turing-gép nem tud kevés, de nem konstans tárhellyel futni. Ha létezne a kérdésben szereplő szuper gyors algoritmus (ami ezért szuper kevés tárhelyet használ fel), akkor egy 1-irányú Turing gép azt felhasználva mégis tudna kevés tárhellyel futni: figyeli a tárhelye méretét, és ha túl nagy, akkor leáll.

(Ez csak egy ötlet-morzsa, láttam már hasonlót, de nem tudom precízen hogy szól, meg hogy hogyan lehet felhasználni. Simán lehet hogy van triviális konstrukció akármilyen könnyen kiszámolható függvényre: könnyen kiszámoljuk hogy meddig kell futni, és addig futunk.(?))

> Megmutatható hogy egy 1-irányú Turing-gép nem tud kevés, de nem konstans tárhellyel futni.

O(log n)-nél kevesebb, o(log n) tárhellyel. Ha nem használ korlátos tárhelyet, akkor vannak olyan inputok, amelyekre egyre több és több tárhelyet használ, és konstruálható olyan bemenetcsalád, amelyre az 1-irányú Turing gép elég gyorsan nyit új tárhelyeket, log i tárhelyet használ, vagy még többet.

Például ez a random egyetemi pdf kimondja hogy nincsen kicsi tárhely bonyolultság:

> In other words, there are no other space complexity classes between the constant space DSPACE(0) and DSPACE(λn. log log n). For example, the class DSPACE(λn. log log log n) does not exist.

[link]

(Csak ő két irányú gépre, én meg 1-irányú gépre.) (Kíváncsi vagyok, ennek mi a neve, fenn van wiki-n, valaki?)

Amiből szerintem már adódik (lásd feljebb), hogy nincsenek szuper gyors algoritmusok, log log n-nél gyorsabbak. Hiszen azok szuper kevés tárhelyet tudnak csak felhasználni. (És akkor most eltekintettünk attól, hogy az inputot jó lenne beolvasni, log n idő alatt.)

> Amiből szerintem már adódik (lásd feljebb), hogy nincsenek szuper gyors algoritmusok, log log n-nél gyorsabbak. Hiszen azok szuper kevés tárhelyet tudnak csak felhasználni.

Inkább: nincsenek szuper gyors algoritmusok, mert azok segítségével lehetne szuper kevés tárhelyet felhasználni (mondjuk futtatni a szuper gyors algoritmust szuper kevés vagy konstans tárhelyen, és minden lépéséhez egy új tárhelyet felhasználni, vagy ilyesmi. Ez szuper kevés tárhely + szuper kevés tárhely, ami még mindig szuper kevés, ami nem lehet.)