Вопросы о космических ресурсах вычислений в вычислительной сложности или алгоритмах.
Это может быть субъективный вопрос, а не конкретный ответ, но в любом случае. В теории сложности мы изучаем понятие эффективных вычислений. Существуют классы, такие как обозначает полиномиальное время , а обозначает пространство журнала . Оба они считаются своего рода «эффективностью», и они...
Определите LOGLOG как класс языков, которые можно вычислить в пространстве O (loglog n) с помощью детерминированной машины Тьюринга (с двусторонним доступом к входу). Аналогично определите NLOGLOG как класс языков, которые могут быть вычислены в пространстве O (log log n) недетерминированной...
ST-связность - это проблема определения, существует ли направленный путь между двумя выделенными вершинами и в ориентированном графе . Может ли эта проблема быть решена в пространстве журналов, является давней открытой проблемой. Это называется проблемой противssstttG(V,E)G(V,E)G(V,E)NLNLNLLLL В...
Прежде всего, заранее прошу прощения за любую глупость. Я ни в коем случае не эксперт по теории сложности (отнюдь! Я студент, берущий свой первый класс по теории сложности). Вот мой вопрос. Теперь теорема Савича гласит, что Теперь мне интересно, если эта нижняя граница была жесткой, то есть это...
Хорошо известно, что направленная st-связность является полной. Прорыв результат Рейнгольд показал , что неориентированный ст-связность в . Известно, что направленная st-связность находится в . Cho и Huynh определили параметризованную задачу о ранце и продемонстрировали иерархию проблем между и...
Ясно, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Существует множество классов сложности между и . Примеры включают , , , , , . Широко распространено мнение , что .P L P N L L o g C F L N C i S A C i A C...
Ширина дерева показывает, насколько близок график к дереву. NP-трудно вычислить ширину дерева. Наиболее известный алгоритм приближения достигает O ( войдите n----√)O(logn)O(\sqrt{{\log}n}) фактор. Теорема Курселя гласит, что любое свойство графов, определяемых в монадической логике второго порядка...
Интересно, есть ли основания полагать, что или верить, что N L ≠ L ?NL = LNL=LNL=LNL ≠ LNL≠LNL\neq L Известно, что . Литература по derandomization из R L является довольно убедительным , что R L = L . Кто-нибудь знает о каких-то статьях или идеях, убеждая, что N L ≠ L ?NL ⊂ L2NL⊂L2NL \subset L^2R...
Исходя из предыдущего вопроса , Каковы наилучшие текущие нижние границы пространства для SAT? С нижней границей пробела здесь я имею в виду количество ячеек рабочей ленты, используемых машиной Тьюринга, которая использует двоичный алфавит рабочей ленты. Постоянный аддитивный член неизбежен,...
Рассмотрим язык E Q UA L I T Y ={ аNбN∣ n ≥ 0 }ЕQUALяTYзнак равно{aNбN|N≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} . Известно, что E Q UA L I T YЕQUALяTY \mathtt{EQUALITY} не может быть распознано ни одной чередующейся машиной Тьюринга (АТМ) с сублогарифмическим пространством (Szepietowski,...
Иммерман и Szelepcsenyi независимо друг от друга доказали , что . Используя метод индуктивного подсчета, Бородин и др. Доказали, что S A C i замкнут при комплементации при i > 0 . До теоремы Рейнгольда ( S L = L ) Нисан и Та-Шма доказали S L = c o S L , используя унифицированные проекции...
В общем, лента запросов для оракула учитывает сложность пространства ТМ. Тем не менее, кажется правдоподобным разрешить запись оракула только для записи (например, которая используется в сокращениях L-пространства). Полезна ли такая конструкция? Дает ли он какие-то особенно абсурдные...
USTCONN - это проблема, которая требует решения о том, существует ли путь от исходной вершины sss до целевой вершины ttt в графе GGG , где все они представлены как часть входных данных. Омер Рейнгольд показал, что USTCONN находится в L (doi: 10.1145 / 1391289.1391291 ). Доказательство создает...
В классической статье Манро и Патерсон изучают проблему того, сколько памяти требуется алгоритму для нахождения медианы в случайно отсортированном массиве. В частности, они ориентированы на следующую модель: ввод читается слева направо в течение числа P раз. Показано, что O ( n12...
Недавно Ватроус и др. Доказали, что QIP (3) = PSPACE - замечательный результат. Это был удивительный результат для меня, если не сказать больше, и это заставило меня задуматься ... Я задавался вопросом, что если бы Quantum Computers могла эффективно моделироваться классическими компьютерами. Может...
Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...
Распределение называется ϵ- обмануть функцию f, если | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . И говорят, что он обманывает класс функций, если он обманывает каждую функцию в этом классе. Известно , что & epsi -biased пространство дурака класс паритетов над подмножествами. (см....
Легко видеть, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Многие известные алгоритмы логарифмического пространства (например, ненаправленная st-связность, изоморфизм плоских графов) работают в где безумно...
Ограниченные во времени квантовые вычисления, очевидно, очень интересны. Как насчет квантовых вычислений, ограниченных пространством? Я знаю много интересных результатов для квантовых вычислений с сублогарифмическими пространственными границами и различными типами моделей квантовых автоматов. С...
Нисан доказал в «Псевдослучайных генераторах для пространственно-ограниченных вычислений», что существует псевдослучайный генератор, который «обманывает» ограниченные в пространстве вычисления. Эта конструкция справедлива для каждого оракула (по крайней мере, для неадаптивных...