Неизвестно, является ли или , гдеP⊆CSLP⊆CSLP\subseteq CSLP⊈CSLP⊈CSLP\not\subseteq CSL PPP - это множество всех языков, разрешимых за полиномиальное время на детерминированной машине Тьюринга, и CSLCSLCSL - это класс контекстно-зависимых языков, который, как известно, эквивалентен...
Elberfeld, Jakoby и Tantau 2010 ( ECCC TR10-062 ) доказали неэффективную версию теоремы Бодлендера. Они показали, что для графов с шириной дерева не более разложение дерева шириной можно найти с помощью логарифмического пространства. Постоянный множитель в границе пространства зависит от k ....
Предположим, что - параметризованный язык относительно некоторого алфавита Σ . К -slice из L является L K = L ∩ { ( х , к ) | х ∈ Е * } , множество экземпляров в L , которые имеют параметр K . Класс сложности X P содержит параметризованные языки L такие, что L k ∈ P для каждого...
Мотивация : Разрабатывая инструменты для управления версиями данных, мы в конечном итоге изучили алгоритмы «различий» двух наборов целых чисел, предложив последовательность преобразований, которые переводят один набор целых чисел в другой. Мы смогли свести эту проблему к следующей очень...
Я заинтересован в определении сложности следующей задачи решения: учитывая два целых числа и l 2 (каждое из которых содержит не более m бит), решить, является ли старший значащий бит умножения l 1 ⋅ l 2 равным 1 (где результат печатается в 2м битах с возможно ведущими 0)?L1L1l_1L2L2l_2L1⋅...
Теорема Махейни говорит нам , что если есть разреженная -полное множество под полиномиальное время многие-одно сокращение, то P = N P . (См. « Разреженные комплекты для NP: Решение гипотезы Бермана и Хартманиса »)NпNPNPP=NPP=NPP = NP Известны ли последствия существования разреженных полных наборов...
Я наткнулся на два примера гипотетической сложности некоторых графовых задач. Гипотетическая твердость означает, что опровержение некоторой гипотезы подразумевает NP-полноту соответствующей задачи графа. Например, гипотеза Барнетта утверждает, что каждый 3-связный кубический плоский двудольный граф...
Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом А . Первоначально A пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MMMAAAAAAxxx Рассмотрим следующую игру Алисы и Боба. Первоначально...
Существует ли алгоритм сортировки, основанный на сравнении, который использует среднее из сравнений ?l g (n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Существование алгоритма сравнения в худшем случае является открытой проблемой, но среднего случая достаточно для рандомизированного алгоритма с...
Существуют ли примеры случаев, когда классическое моделирование квантового алгоритма для задачи превосходит лучший ранее известный классический алгоритм для этой задачи? «Превосходит» не обязательно означает другой класс сложности, это может быть просто лучшее масштабирование. Этот вопрос был...
В настоящее время я ищу предмет для диссертации и столкнулся с областью алгоритмической теории информации. Поле кажется мне очень интересным, но, кажется, все поле было сделано за много лет. Итак, мой вопрос: поле «живое» или оно в значительной степени закрыто? Есть ли у него открытые вопросы?...
Класс NCiNCi\textrm{NC}^i является классом функций, вычисляемых семействами схем ограниченного вкручивания, размера nO(1)nO(1)n^{O(1)} и глубины O(logi(n))O(logi(n))O(\log^i(n)) . NCNC\textrm{NC} -hierarchy является объединением этих классов. Есть ли какое-либо исследование линейного размера этой...
Это обобщение моего предыдущего вопроса . Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом . Первоначально пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MMMAAAAAAxИксx Рассмотрим...
С начала 70-х годов известно, что и не равны (потому что не является замкнутым в полиномиальном времени многих одно сокращение, в отличие от ). Однако, насколько мне известно, до сих пор не ясно, является ли один класс подмножеством другого, или они несопоставимы, то есть и оба непусты.NPNP{\bf...
Мы знаем, что в мы не можем решить SUM за время при любой функции (обычно ).ЕTЧАСЕTЧАСETHККKе( К) Р о л у( п К)е(К)поLY(NК)f(K)poly(nK)е( К)е(К)f(K)2О ( К)2О(К)2^{O(K)} Существует ли какая-либо гипотеза, которая предотвращает сложность (это полностью согласуется с возможностью, так как нам нужно...
Задача двухцветного идеального сопоставления состоит в том, чтобы решить, имеет ли граф раскраску с двумя цветами, чтобы у каждого узла был ровно один сосед того же цвета, что и он сам. Шефер доказал, что задача является NP-полной . Он остается NP-полным даже для плоских кубических графов. Меня...
Существуют ли какие-либо известные результаты, показывающие, что существование (или несуществование) конечных графов с конкретными вычислимыми свойствами подразумевает определенные результаты сложности (такие как P = NP)? Вот один полностью гипотетический результат: если существует конечный граф с...
IP (2pfa) и AM (2pfa) - это классы языков, распознаваемые с ограниченной ошибкой в частных и открытых версиях монет, соответственно, интерактивных систем доказательства с верификаторами, которые являются вероятностными конечными автоматами с двусторонней входной головкой. Известны ли какие-либо...
Умножение матриц с использованием обычной техники (ряд - столбец) занимает O (N3)O(n3)O(n^{3}) умножение и O (N3)O(n3)O(n^{3})дополнения. Однако при условии, что записи равного размера (количество битов в каждой записи обеих матриц умножается) размерамmm биты, операция сложения на самом деле...
Теория сложности вычислений классифицирует проблемы в соответствии с их сложностью. Теория сложных систем обращается к системам, которые демонстрируют поведение, которое, очевидно, не вытекает из свойств отдельных частей системы. Примеры включают хаотические системы, сложные адаптивные системы или...