Известно, что показатель TSP может быть аппроксимирован в пределах и не может быть аппроксимирован лучше, чем за полиномиальное время. Известно ли что-нибудь о поиске аппроксимационных решений за экспоненциальное время (например, менее шагов только с полиномиальным пространством)? Например, в какое...
Граф является выбираемым (также известным как -list-colourable ), если для каждой функции которая отображает вершины в наборы из цветов, существует такое цветовое присвоение , что для всех вершин , , и такие , что для всех ребер Vw , с (v) \ п с (ш) .k f k c v c ( v ) ∈ f ( v ) v w c ( v ) ≠ c ( w...
Классические алгоритмы могут решать 3-SAT за времени (рандомизированный) или времени (детерминированный). (Ссылка: лучшие верхние границы по SAT )1,3071N1,3071N1.3071^n1,3303N1,3303N1.3303^n Для сравнения, используя алгоритм Гровера на квантовом компьютере, можно было бы найти и найти решение в ,...
Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем O∗(2n)O∗(2n)O^*(2^n) ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP? UPD: подавляет полиномиальные факторы.O∗(⋅)O∗(⋅)O^*(\cdot) Самая короткая...
Рассмотрим следующую проблему решения Входные данные : монотонный CNF ΦΦ\Phi и монотонный DNF ΨΨ\Psi . Вопрос : Φ→ΨΦ→Ψ\Phi \to \Psi тавтология? Определенно вы можете решить эту проблему в O(2n⋅poly(l))O(2n⋅poly(l))O(2^n \cdot \mathrm{poly}(l)) -time, где nnn - количество переменных в Φ→ΨΦ→Ψ\Phi \to...
Этот вопрос о задачах квадратичного программирования с коробочными ограничениями (box-QP), т. Е. Задачах оптимизации вида минимизировать учетом x ∈ [ 0 , 1 ] n .f(x)=xTAx+cTxf(x)=xTAx+cTxf(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}x∈[0,1]nx∈[0,1]n\mathbf{x} \in [0,1]^n Если...
Знаете ли вы о каких-либо проблемах (предпочтительно, по крайней мере, несколько хорошо известных), где для практического размера задачи экспоненциальный алгоритм работает намного быстрее, чем самый известный аналог полиномиального времени. Например, предположим, что задача имеет практический...
Возможно ли, что ? Есть ли интересные последствия такого сдерживания? Будет ли это противоречить гипотезе экспоненциального времени?SAT¯¯¯¯¯¯¯¯¯¯∈NTIME(exp(n0.9))SAT¯∈NTIME(exp(n0.9))\overline{SAT} \in...
Impagliazzo, Paturi и Calabro, Impagliazzo, Paturi представили гипотезу экспоненциального времени (ETH) и гипотезу сильно экспоненциального времени (SETH). Грубо говоря, SETH говорит, что нет алгоритма, который решает SAT за время . 1.99n1.99n1.99^n Мне было интересно, что бы это значило, чтобы...
Исправить . Для любого достаточно большого мы хотели бы пометить все подмножества размера точно натуральными числами из . Нам бы хотелось, чтобы эта маркировка удовлетворяла следующему свойству: есть множество целых чисел, stk≥5k≥5k\ge5nnn{1..n}{1..n}\{1..n\}n/kn/kn/k{1...T}{1...T}\{1...T\}SSS Если...
Существуют ли известные алгоритмы для следующей задачи, которые побеждают наивный алгоритм? Вход: система из m линейных неравенств.Ax≤bAx≤bAx \le bmmm Вывод: выполнимое решение если оно существует.x∗∈{0,1}nx∗∈{0,1}nx^*\in \{0,1 \}^n Предположим, что и b имеют целочисленные записи. Меня интересуют...
Насколько сложна проблема Set Cover, если число элементов ограничено некоторой функцией (например, ), где - размер экземпляра задачи. Формально,nlognlogn\log nnnn Пусть и где и . Насколько сложно решить следующую проблему?F = { S 1 , ⋯ , S n } S i ⊆ U m = O ( log n )U= { е1, ⋯ ,...
Означает ли тот факт, что проблема полна по времени EXP, означает, что A не находится в D T I M E ( 2 o ( n ) ) ?AAAAAAД ТяMЕ( 2o ( n ))DTIME(2o(n))DTIME(2^{o(n)}) Мне известно, что по теореме временной иерархии не входит в E = D T I M E ( 2 O ( n ) ) . Тем не менее это, по-видимому, не исключает...
Когда я посмотрел « Динамический программный подход к решению задач секвенирования » Майкла Хелда и Ричарда М. Карпа, у меня возник следующий вопрос: почему сложность их алгоритма для TSP равна (∑n−1k=2k(k−1)(n−1k))+(n−1)(∑k=2n−1k(k−1)(n−1k))+(n−1)(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1) (стр....
Существуют ли известные алгоритмы для следующей задачи, которые побеждают наивный алгоритм? Входные данные: матрица и векторы , где все элементы являются неотрицательными целыми числами.AAAb,cb,cb,cA,b,cA,b,cA,b,c Вывод: оптимальное решение от до...