полиЛ

В сложности вычислений теории полиL — это класс сложности задач решения , которые могут быть решены на детерминированной машине Тьюринга с помощью алгоритма, пространственная сложность которого ограничена полилогарифмической функцией от размера входных данных. Другими словами, polyL = DSPACE ((log n ) ^О(1) ), где n обозначает входной размер, а O (1) обозначает константу.

Так же, как L ⊆ P , полиL ⊆ QP . Однако единственная доказанная связь между полиL и P состоит в том, что полиL ≠ P ; неизвестно, полиL ⊊ P , P ⊊ полиL или ни один из них не содержится в другом. Одним из доказательств того, что polyL ≠ P, является то, что P имеет полную проблему при логарифмическом пространственном сокращении «много-один», но PolyL не имеет такой проблемы из-за теоремы о пространственной иерархии . Теорема о пространственной иерархии гарантирует, что DSPACE (log ^д n ) ⊊ DSPACE (лог . ^{д + 1} n ) для всех целых чисел d > 0. Если бы у PolyL была полная проблема, назовите ее A , это был бы элемент DSPACE (log ^к n ) для некоторого целого числа k > 0. Предположим, что задача B является элементом DSPACE (log ^{к + 1} n ) \ DSPACE (журнал ^к н ). Предположение о полноте A влечет за собой следующее O(log ^к n ) пространственный алгоритм для B : уменьшить B до A в логарифмическом пространстве, затем решить A в O(log ^к п ) пространство. Это означает, что B является элементом DSPACE (log ^к n ) и, следовательно, нарушает теорему о пространственной иерархии.

Отсутствие полных задач для полиL в логарифмическом пространстве при сокращении до числа единиц привело Ферраротти и др. определить другое понятие полноты для этого класса, включая преобразования от параметризованных задач к машинам с полилогическим пространством, которые решают проблемы для конкретных значений параметров.