Определение «проблемы» , чтобы быть алгоритм принимает натуральное число и возвращает 0 или 1 , который возвращает 1 , по меньшей мере , одной п ∈ N . Любое такое n называется «решением» AAAA111n∈Nn∈Nn \in \mathbb{N}nnnAAA Определите «универсальный решатель проблем» как алгоритм принимающий...
Дан ориентированный граф с n узлами, такими, что каждая вершина имеет ровно два исходящих ребра, и натуральное число N, закодированное в двоичном виде, две вершины s и t, Я хочу посчитать количество (не обязательно простых) путей от s до t в течение N шагов. Это # P-сложная проблема? Или вообще, в...
Известно, что нижняя граница общего противника характеризует сложность квантового запроса благодаря прорывной работе Reichardt et al. Та же самая линия работы также устанавливает связи со структурой программы span для разработки квантовых алгоритмов. Многие интересные квантовые алгоритмы, включая...
Если нам даны две строки размером и , стандартное вычисление расстояния редактирования Левенштейна выполняется с помощью динамического алгоритма с временной сложностью и пространственной сложностью . (Некоторые улучшения могут быть сделаны в зависимости от расстояния редактирования , но мы не...
Были предприняты некоторые попытки решить проблему изоморфизма графов с помощью квантового случайного блуждания жестких бозонов (симметричное, но без двойного заполнения). Симметричная степень матрицы смежности, которая казалась многообещающей, оказалась неполной для общих графов в этой статье...
ETH утверждает, что SAT не может быть решена в худшем случае за субэкспоненциальное время. Как насчет среднего случая? Есть ли естественные проблемы в NP, которые предположительно будут экспоненциально сложными в среднем случае? Возьмите средний случай, чтобы означать среднее время работы с...
Зафиксируем NP-полную задачу поиска, например форму поиска SAT. Поиск Левина предоставляет алгоритм L для решения X, который в некотором смысле является оптимальным. В частности, алгоритм таков: «Выполните все возможные программы P в соответствии друг с другом на входе x , как только некоторые P...
широко предположительно, чтобы быть ложным.R P= NпRP=NPRP = NP Но представьте на мгновение, что это правда. В таком случае, насколько вероятно, что ?п= NпP=NPP = NP Другими словами: в мире, где , что еще может помешать нам верить P = N P ?R P= NпRP=NPRP = NPп= NпP=NPP =...
Теорема Шефера о дихотомии показывает, что каждая задача CSP над либо разрешима за полиномиальное время, либо NP-полна. Это относится только к задачам CSP с ограниченной шириной, за исключением, например, SAT и Horn-SAT. Общие проблемы CSP с неограниченной шириной могут быть очень сложными (даже не...
Я ищу результаты твердости по раскраске вершин графов с ограниченной степенью. Учитывая граф , мы знаем, что для любого ϵ > 0 трудно приблизить χ ( G ) с множителем | V | 1 - ϵ, если NP = ZPP [ 1 ]. Но что, если максимальная степень G ограничена d ? Существуют ли в этом случае коэффициенты...
Судоку - это хорошо известная головоломка, которая является NP-полной. Двоичный судоку - это вариант, который допускает только цифры и 1 . Правила следующие.000111 Каждая строка и каждый столбец должны содержать одинаковое количество нулей и единиц. Каждая строка и каждый столбец уникальны. Ни одна...
Определите как класс языков, которые могут быть приняты машиной (множественной) Тьюринга за время f ( n ) + 1 . (« + 1 » просто для упрощения обозначений и предотвращения путаницы.) Обратите внимание, что вокруг f ( n ) + 1 нет O ( ⋅ ) .D T I M E (f( н ) )DTяMЕ(е(N))\mathsf{DTIME}(f(n))е( n ) +...
Сглаженный анализ был применен много раз, чтобы понять время выполнения точных алгоритмов для многих задач, таких как линейное программирование и k-средних. В этой области есть довольно общие результаты, например, Хейко Рёглин и Бертольд Вёкинг, Сглаженный анализ целочисленного программирования ,...
Какая связь между PLSPLS\mathsf{PLS} и APXAPX\mathsf{APX} ? Другими словами, аппроксимируются ли задачи, допускающие локальный поиск за полиномиальное время? Означают ли приближенные задачи оптимизации алгоритм локального поиска...
Учитывая детерминированную игру с нулевой суммой частичной информации только с конечным числом состояний, чьи возможные результаты [проиграть, сыграть, выиграть] со значениями [-1,0, + 1] соответственно, какова сложность аппроксимации значения такого игра аддитивно в ?ϵϵ\epsilon В частности, я не...
Знаем ли мы, что иерархия не разрушается ( T C 0 d ⊊ T C 0 d + 1 для всех d )?Т С0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd В записи Zoo для TC0TC0\mathsf{TC^0} упоминается только расстояние между глубиной 2 и 3. Кроме того, есть стандартная ссылка на...
Этот вопрос мотивирован этим постом, Можете ли вы определить сумму двух перестановок за полиномиальное время? и мой интерес к вычислительным свойствам перестановок. Разностная последовательность перестановки чисел формируется путем нахождения разности между каждыми двумя соседними числами в...
Остаточные автоматы в конечном состоянии (RFSA, определенные в [DLT02]) - это NFA, которые имеют некоторые общие черты с DFA. В частности, для каждого обычного языка всегда существует канонический RFSA минимального размера, а язык, распознаваемый каждым государством в RFSA, является остаточным, как...
Содержится в-между каждым уровнем многочлена иерархии различные классы сложности, в том числе ΔPiΔiP\Delta_i^{\text{P}} , DPDP\text{DP} , BHkBHk\text{BH}_k , и ΣPi∩ΠPiΣiP∩ΠiP\Sigma_i^\text{P} \cap \Pi_i^\text{P} . Из-за отсутствия лучшей терминологии я буду ссылаться на эти и любые другие как...
Недавно я начал много читать о сложности доказательств, и мне очень понравилось то, что я читал. Я действительно хотел бы узнать больше об этом, но мне трудно найти хороший материал для начинающих. Кто-нибудь сможет порекомендовать некоторые...