Хорошо известно, что палиндромы могут распознаваться в линейном времени на машинах Тьюринга с лентами, но не на машинах Тьюринга с одной лентой (в этом случае необходимое время является квадратичным). Алгоритм линейного времени использует копию входных данных и, следовательно, также использует...
Какова наиболее известная сложность для вычисления точного расстояния редактирования между двумя строками одинаковой длины с использованием рабочего пространства, которое является сублинейным по размеру ввода? Я предполагаю, что вход хранится в каком-то формате только для чтения. Это ранее...
Легко видеть, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Многие известные алгоритмы логарифмического пространства (например, ненаправленная st-связность, изоморфизм плоских графов) работают в где безумно...
Рассмотрим такой язык LLL , что: L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) и так что L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Другими словами, самая быстрая машина...
Я интересуюсь ранней историей опубликованных результатов о пространственно-временных компромиссах общего назначения. В частности, я хочу знать, кто первым описал следующий тип алгоритма для вычисления вычисления, имеющего произвольный граф потока данных с степенью O (1), используя пространство,...
(уже просили на главном сайте , но просим также о лучшем освещении, извините) Так как я знал о сжатых структурах данных, мне отчаянно нужен хороший обзор последних событий в этой области. Я погуглил и прочитал много статей, которые я мог видеть в верхней части результатов Google по запросам сверху...
Может ли недетерминизм ускорить детерминистские вычисления? Если да, то сколько? Под ускорением детерминированных вычислений недетерминизмом я подразумеваю результаты вида: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Например, что-то вроде...
После обсуждения нижних границ для 3SAT [ 1 ] мне интересно, каковы основные результаты нижней границы, сформулированные как компромиссы пространства-времени. Я исключаю такие результаты, как, например, теорема Савича; хорошая статья будет сосредоточена на одной проблеме и ее границах. Примером...
Если нам даны две строки размером и , стандартное вычисление расстояния редактирования Левенштейна выполняется с помощью динамического алгоритма с временной сложностью и пространственной сложностью . (Некоторые улучшения могут быть сделаны в зависимости от расстояния редактирования , но мы не...
Здесь было несколько вопросов ( 1 , 2 , 3 ) о транзитивном завершении, которые заставили меня задуматься, возможно ли что-то подобное: Предположим, мы получили входной ориентированный граф GGG и хотел бы ответить на запросы типа "(u,v)∈G+(u,v)∈G+(u,v)\in G^+? ", т.е. спрашивает, существует ли ребро...
Это продолжение недетерминированного ускорения детерминированных вычислений . Возможно ли, что недетерминизм (или, в более общем смысле, чередование) позволил бы общее квадратичное ускорение детерминированных вычислений? Или есть какие-то известные неправдоподобные последствия для чего-то вроде...