и N L o g T i m e - два самых маленьких класса сложности, которые мы имеем. (Обратите внимание, что логарифмическая иерархия времени L H равна A C 0, и это первые два уровня L H ).DLogTimeDLogTime\mathsf{DLogTime}NLogTimeNLogTime\mathsf{NLogTime}LHLH\mathsf{LH}AC0AC0\mathsf{AC}^0LHLH\mathsf{LH}...
Вот проблема: У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата. Примеры: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Эта проблема NP-полная? Если да, как я могу это...
Пусть класс графов с ограниченной шириной клика. В каждом графе в некоторые ребра сжимаются (например, случайно). Теперь ширина клики все еще ограничена?GGGGGG Если это (вообще) больше не ограничено, я был бы очень заинтересован в...
Недавно я изучал введение в голографические алгоритмы. Я столкнулся с некоторыми комбинаторными объектами, которые называются пфаффианцами. Я не очень много знаю о них на данный момент и натолкнулся на некоторые неожиданные способы их использования. Например, я узнал, что их можно использовать для...
Пытаясь решить проблему, я выразил ее часть в виде следующей целочисленной линейной программы. Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных x i j устанавливается в ноль, а остальные могут принимать положительные целые...
Наблюдение, связанное с асимметричной криптографией, заключается в том, что некоторые функции (как полагают) легко выполнять в одном направлении, но трудно инвертировать. Кроме того, если существует некоторая информация о «ловушке», которая позволяет быстро вычислять обратную операцию, тогда...
Теория компилятора, кажется, довольно проверенная тема. Какие открытые проблемы или текущие исследования происходят в этой
Покрытие Vertex может быть легко уменьшено до Независимого набора и наоборот. Однако в контексте параметризованной сложности Независимый набор сложнее, чем Vertex Cover. Ядро с вершин существует для Vertex Cover, но независимое множество W 1 жестких.2k2k2k Как меняется характер Независимого...
Я обнаружил, что маркированные переходные системы являются хорошей моделью для моего приложения, а именно есть статья о моделировании вариантов использования с использованием LTS. Вопрос в том, что можно легко доказать о LTS? Я хотел бы повторно использовать существующие решения, чтобы увидеть,...
Это связано с общим вопросом « Как мне рецензировать статью? ». Я рецензирую статью для конференции, и эту статью следует отклонить, поскольку она недостаточно значима для публикации и имеет недостатки в некоторых технических деталях. Бумага не ошибается, но способы, которыми она правильна, не...
Хорошо известно, что в худшем случае существует оптимальный алгоритм для вычисления кода Хаффмана за время θ ( н лгн )θ(NЛ.Г.N)\theta(n\lg n) . Это улучшается двумя ортогональными способами: Оптимальные коды без префиксов могут быть вычислены быстрее, если набор различных частот мал (например,...
Генетические алгоритмы развиваются в меньшем количестве поколений с большей популяцией, но также требуют больше времени для вычисления поколения. Существуют ли какие-то руководящие принципы для уравновешивания этих двух факторов, чтобы как можно скорее найти жизнеспособное решение? Кроме того, это...
Я пробовал следующее расслабление LP максимального независимого набора max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Я получаю 1/21/21/2 для каждой переменной для каждого кубического недвудольного графа Я...
Если предположить, что NP! = CoNP, то для проблемы полного завершения coNP нет сертификата полиномиального размера. Но как насчет субэкспоненциального размера сертификата? Особенно для coSAT, есть ли субэкспоненциальное доказательство размера, чтобы доказать, что формула неудовлетворительна? Если...
Фиксированный параметр и аппроксимация - это совершенно разные подходы для решения сложных задач. У них разная мотивация. Приближение ищет более быстрый результат с приближенным решением. Фиксированный параметр ищет точное решение с временной сложностью в терминах экспоненциальной или некоторой...
То, что я называю подсчетом, - это проблема, заключающаяся в том, чтобы найти количество решений для функции. Точнее, если задана функция f:N→{0,1}f:N→{0,1}f:N\to \{0,1\} (не обязательно черный ящик), приблизительный #{x∈N∣f(x)=1}=|f−1(1)|#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|,...
Даны монет номиналом, с c 1 = 1 и c 2 < c 3 < . , < c n - случайные числа, равномерно распределенные в диапазоне [ 2 , N ] . Асимптотически, для какой доли монет жадный алгоритм генерирует оптимальное изменение, используя этот набор номиналов?NNnс1= 1с1знак равно1c_1=1с2< с3< . ,...
Я начинаю исследовать возможность использования решателя SAT для решения интересующей меня проблемы оптимизации, и в настоящее время я ищу опрос, который будет содержать примеры «умных» преобразований в варианты SAT (то есть преобразований, которые приводят к в задаче разумного размера, так как...
Каждый раз, когда я преподаю NP-Полноту, студенты спрашивают: «Есть ли проблемы, о которых известно, что они не относятся к NP?» Как бы вы ответили? Я обычно даю им неразрешимую проблему в качестве примера, но это часто не очень хорошо получается: (а) если я дам им проблему остановки, они думают,...
Рассмотрим следующую проблему - С учетом максимальной плоских графов и G 2 , найти граф с максимальным числом ребер таким образом, что существует подграф (не обязательно индуцируется) в обоих и , изоморфная .G1G1G_1G2G2G_2GGGG1G1G_1G2G2G_2GGG Можно ли это сделать за полиномиальное время? Если да,...