L/poli

W teorii złożoności obliczeniowej L/poly jest klasą złożoności logarytmicznych maszyn kosmicznych z wielomianową ilością porad . L/poly jest niejednorodną logarytmiczną klasą przestrzeni, analogiczną do niejednorodnej wielomianowej klasy czasowej P/poly .

Formalnie, aby język formalny L należał do L/poly, musi istnieć funkcja doradcza f , która odwzorowuje liczbę całkowitą n na łańcuch o długości wielomianu w n , oraz maszyna Turinga M z dwiema taśmami wejściowymi tylko do odczytu i jedną taśmą do odczytu -napisz taśmę o rozmiarze logarytmicznym w rozmiarze wejściowym, tak że wejście x o długości n należy do L wtedy i tylko wtedy, gdy maszyna M akceptuje wejście x , f ( n ) . Alternatywnie i prościej, L jest w L/poly wtedy i tylko wtedy, gdy może być rozpoznane przez programy rozgałęziające o wielkości wielomianu. Jednym z kierunków dowodu, że te dwa modele obliczeń są równoważne pod względem mocy, jest obserwacja, że ​​​​jeśli istnieje program rozgałęziający o rozmiarze wielomianu, można go określić za pomocą funkcji doradczej i symulować za pomocą maszyny Turinga. W przeciwnym kierunku maszyna Turinga z logarytmiczną zapisywalną przestrzenią i wielomianową taśmą doradczą może być symulowana przez program rozgałęziający, którego stany reprezentują kombinację konfiguracji zapisywalnej taśmy i położenia głowic maszyny Turinga na pozostałych dwóch taśmy.

W 1979 roku Aleliunas i in. wykazało, że symetryczna przestrzeń logarytmiczna jest zawarta w L/poly. Jednak wynik ten został zastąpiony przez wynik Omera Reingolda , że ​​SL zapada się do jednolitej przestrzeni logów.

BPL jest zawarte w L/poly, które jest wariantem twierdzenia Adlemana .