Анализ наихудших и средних случаев - это общеизвестные меры сложности алгоритма. Недавно сглаженный анализ стал еще одной парадигмой, объясняющей, почему некоторые алгоритмы, экспоненциальные в наихудшем случае, так хорошо работают на практике, например, симплексный алгоритм. Мой вопрос - есть ли...
Является ли следующая проблема в PTIME или coNP-hard: Даны два булевых выражения и в переменных без отрицания (т. Е. Выражения полностью построены с помощью и ). Решите, есть ли , то есть имеют ли они одинаковое значение для всех назначений переменных.е1е1e_1е2е2e_2Икс1, … ,...
Я ищу проблему, которая принадлежит в общих графах, но находится в в графах с ограниченной шириной дерева. На самом деле я думаю, что эти проблемы сложнее, чем использование нормального динамического программирования в ограниченных графах. -ширины графиков для их...
Какое минимальное количество двоичных вентилей необходимо для вычисления И и ИЛИ из входных битов одновременно? Тривиальная верхняя граница . Я считаю, что это оптимально, но как это доказать? Стандартный метод устранения строба здесь не работает, так как, присваивая константу любой из входных...
Классическим результатом Куроды является то, что класс сложности NSPACE [ ]NNn (также известный как NLIN-SPACE) является именно классом CSL контекстно-зависимых языков . Задача выполнимости SAT находится в NSPACE [ ], так как предположение линейного размера для решения может быть проверено не более...
Меня интересует эта проблема: учитывая неориентированный граф , существует ли разбиение G на графы G 1 ( E 1 , V 1 ) и G 2 ( E 2 , V 2 ), такие что G 1 а G 2 изоморфны?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Здесь разбивается на два...
Мне было интересно, можно ли охарактеризовать проблемы, для которых существуют алгоритмы сублинейного времени (в размере входных данных) как обладающие определенными свойствами. Это включает в себя сублинейное время (например, тестирование свойств, альтернативное понятие аппроксимации для задач...
Не известно , если изоморфизм графов (GI) для сильно регулярных графов (SRGS) в P . Есть ли намеки на то, что это может или не может быть GI- Complete? Есть ли сильные последствия в таких случаях? (Аналогично убеждению, что GI не может быть...
В задаче прямоугольник упаковки, один дается набор прямоугольников и ограничивающий прямоугольник R . Задача состоит в том, чтобы найти расположение r 1 , … , r n внутри R так , чтобы ни один из n прямоугольников не перекрывался. Как правило, ориентация каждого прямоугольника г я фиксируется. То...
Предположим, что для каждого ϵ>0ϵ>0\epsilon > 0 существует машина Тьюринга MϵMϵM_{\epsilon} которая определяет язык LLL во времени O(na+ϵ)O(na+ϵ)O(n^{a + \epsilon}) . Существует ли единственный алгоритм, определяющий LLL во времени O(na+o(1))O(na+o(1))O(n^{a + o(1)}) ? (Здесь член...
Я не обладаю знаниями в области теории сложности с участием групп, поэтому я прошу прощения, если это хорошо известный результат. Вопрос 1. Пусть - простой неориентированный граф порядка n . Какова вычислительная сложность (с точки зрения n ) определения, если GGGGnnnnnnGGG вершинно-транзитивным?...
Предположим , что P ≠ N Pп≠Nп\mathsf{P} \neq \mathsf{NP} . N P INпя\mathsf{NPI} - класс задач в Н ПNп\mathsf{NP} которых нет ни в пп\mathsf{P} ни в Н ПNп\mathsf{NP} -твердых. Вы можете найти список проблем предположительно N P INпя\mathsf{NPI} здесь . Теорема Ладнера говорит нам, что если то...
n×nn×nn\times nlog2(n)log2(n)\log^2(n)111∥A∥≤1‖A‖≤1\left\|A\right\|\leq 11/poly1/poly1/\text{poly} В этом отношении, какое «правильное» приближение нужно запрашивать - мультипликативное или аддитивное? (см. один из ответов...
Вышла новая статья, утверждающая квазиполиномиальный алгоритм для дискретного логарифма. http://arxiv.org/abs/1306.4244 Если все верно, значит ли это, что у нас больше нет экспоненциального разделения по сложности классического алгоритма и его квантовой версии для задачи дискретного логарифма?...
Существует очень мало информации, которую я могу найти по NP-полной задаче решения линейного диофантового уравнения в неотрицательных целых числах. То есть, есть решение в неотрицательном к уравнению 1 х 1 + 2 х 2 + . , , + a n x n = b , где все константы положительны? Единственное заслуживающее...
Гауэрс недавно изложил проблему, которую он называет «дискретизированной определенностью Бореля», решение которой связано с доказательством нижних границ схемы. Можете ли вы дать краткое изложение подхода, ориентированного на аудиторию теоретиков сложности? Что потребуется для этого подхода, чтобы...
Однозначные конечные автоматы (UFA) - это особый тип недетерминированных конечных автоматов (NFA). NFA называется однозначным, если каждое слово имеет не более одного приемлемого пути.w ∈ Σ*вес∈Σ*w\in \Sigma^* Это означает , что .D FA ⊂ UFA ⊂ NFADFA⊂UFA⊂NFADFA\subset UFA\subset NFA Известные...
Я ищу проблемы, которые, как известно, являются NPC для ориентированных графов, но имеют полиномиальный алгоритм для неориентированных графов. Я видел вопрос, касающийся здесь «направленных» проблем, которые проще, чем их «ненаправленный» вариант , но я ищу жесткость на направленной стороне....
Теоремы об иерархии являются фундаментальными инструментами. Многие из них были собраны в предыдущем вопросе (см. Какие иерархии и / или теоремы иерархии вы знаете? ). Некоторые разделения классов сложности прямо следуют из теорем иерархии. Примеры таких хорошо известных разделений: , , ,...
NP в ?DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log