L кешендігі (логарифмдік кеңістік): есептерді шешу үшін логарифмдік жадты қолданатын детерминистік Тьюринг машинасы. L = SL, USTCON мәселесі туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Күрделілік класы (логарифмдік кеңістік)
Complexity class (logarithmic space)
Есептеу күрделілігі теориясында L (сондай-ақ LSPACE немесе DLOGSPACE деп аталады) – жазбаға болатын жад кеңістігінің логарифмдік мөлшерін пайдалана отырып, детерминистік Тьюринг машинасымен шешілетін шешімдік есептерді қамтитын күрделілік класы. Формальды түрде, Тьюринг машинасының екі таспасы бар, олардың біреуі кірісті кодтайды және тек оқуға ғана болады, ал екінші таспа логарифмдік өлшемге ие, бірақ оқуға да, жазуға да болады. Логарифмдік кеңістік кіріске тұрақты көрсеткіштер санын сақтауға жеткілікті, сондықтан L толықтығының мағыналы ұғымдарын анықтау үшін әлсіз редукциялар қажет, ең көп тарағаны – бірінші реттік редукциялар. Омер Рейнгольдтың 2004 жылғы нәтижесі USTCON, яғни берілген бағытталмаған графтың екі төбесі арасында жолдың бар-жоқтығын анықтау мәселесі L класына жататынын көрсетеді, бұл L = SL екенін білдіреді, себебі USTCON – SL толық. Мұның бір салдары – L-дің қарапайым логикалық сипаттамасы: ол бірінші реттік логикада коммутативті транзитивті жабылу операторымен (граф теориялық тұрғыдан алғанда, бұл әрбір байланысты компонентті кликаға айналдырады) өрнектелетін тілдерді қамтиды. Бұл нәтиже дерекқор сұраныстары тілдеріне де қолданылады: сұраныстың дерек күрделілігі – дерек көлемін өзгермелі кіріс ретінде қарастыра отырып, белгілі бір сұранысқа жауап берудің күрделілігі ретінде анықталады. Осы өлшем бойынша, толық ақпаратты (нольдер туралы түсініксіздік болмайтын) реляциялық дерекқорларға қатысты сұраулар, мысалы, реляциялық алгебрада көрсетілгендей, L класына жатады.
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input so weaker reductions are required to identify meaningful notions of L completeness, the most common being first order reductions. A 2004 result by Omer Reingold shows that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is in L, showing that L = SL, since USTCON is SL complete. One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first order logic with an added commutative transitive closure operator (in graph theoretical terms, this turns every connected component into a clique). This result has application to database query languages: data complexity of a query is defined as the complexity of answering a fixed query considering the data size as the variable input. For this measure, queries against relational databases with complete information (having no notion of nulls) as expressed for instance in relational algebra are in L.
Қосымша қасиеттері
L өзі үшін төмен, себебі ол журналдық кеңістікте логарифмдік кеңістік оракул сұрауларын (шамамен айтқанда, "логарифмдік кеңістік қолданатын функция шақыруларын") симуляциялай алады, әр сұраныс үшін бірдей кеңістікті қайта қолданады.
L is low for itself, because it can simulate log space oracle queries (roughly speaking, "function calls which use log space") in log space, reusing the same space for each query.
Басқа қолданыстар
Логкеңістіктің негізгі идеясы – логкеңістікте көпмүшелік дәрежелі шаманы сақтау және оны кірістің орнына нұсқауларды есте сақтау үшін пайдалану. Сондықтан, логкеңістік класы компьютердің жедел жадына (RAM) сыймайтын кіріс мәліметтерін модельдеу үшін пайдалы. Ұзын ДНК тізбектері мен деректер базалары – бұл белгілі бір уақытта RAM-да кірістің тек тұрақты бөлігі болатын және кірістің келесі бөлігін қарастыру үшін нұсқаулар болатын, соның арқасында тек логарифмдік жадты пайдаланатын мәселелердің жақсы мысалдары.
The main idea of logspace is that one can store a polynomial magnitude number in logspace and use it to remember pointers to a position of the input. The logspace class is therefore useful to model computation where the input is too big to fit in the RAM of a computer. Long DNA sequences and databases are good examples of problems where only a constant part of the input will be in RAM at a given time and where we have pointers to compute the next part of the input to inspect, thus using only logarithmic memory.