L / poly - L/poly

I beregningskompleksitet teori , L / poly er kompleksiteten klasse av logaritmiske plass maskiner med et polynom mengde råd . L / poly er en ikke-uniform logaritmisk romklasse, analog med den ikke-ensartede polynomiske tidsklassen P / poly .

Formelt sett, for at et formelt språk L skal tilhøre L / poly, må det eksistere en rådsfunksjon f som tilordner et heltall n til en streng med lengdepolynom i n , og en Turing-maskin M med to skrivebeskyttede inngangsbånd og en lest -skriver tape med størrelse logaritmisk i inngangsstørrelsen, slik at en inngang x med lengden n tilhører L hvis og bare hvis maskin M godtar inngangen x ,  f ( n ) . Alternativt og enklere er L i L / poly hvis og bare hvis det kan gjenkjennes av forgreningsprogrammer av polynomisk størrelse. En retning for beviset på at disse to beregningsmodellene er ekvivalente i kraft er observasjonen at hvis det eksisterer et forgreningsprogram med polynomstørrelse, kan det spesifiseres av rådsfunksjonen og simuleres av Turing-maskinen. I den andre retningen kan en Turing-maskin med logaritmisk skrivbar plass og et polynomisk rådgivningstape simuleres av et forgreningsprogram, hvis tilstand representerer kombinasjonen av konfigurasjonen av det skrivbare båndet og posisjonen til Turing-maskinhodene på de to andre. bånd.

I 1979 ble Aleliunas et al. viste at symmetrisk logrom er inneholdt i L / poly. Imidlertid ble dette resultatet erstattet av Omer Reingolds resultat om at SL kollapser til ensartet logarom.

BPL er inneholdt i L / poly, som er en variant av Adlemans teorem .

Referanser