Позвольте мне начать с замечания, что это домашняя проблема. Пожалуйста, предоставьте только рекомендации и соответствующие замечания, НИКАКИХ ПРЯМЫХ ОТВЕТОВ, пожалуйста . С учетом сказанного, вот проблема, на которую я смотрю: Пусть HALF-CLIQUE = { | G является неориентированным графом, имеющим...
Может быть, это довольно просто, но у меня есть некоторые проблемы, чтобы получить это сокращение. Я хочу уменьшить Subset Sum до Partition, но в настоящее время я не вижу связи! Можно ли уменьшить эту проблему с помощью редукции Левина? Если не понимаешь, пиши для...
По словам Иммермана , класс сложности, связанный с запросами SQL, - это в точности класс безопасных запросов в (запросы первого порядка плюс оператор подсчета): SQL захватывает безопасные запросы. (Другими словами, все запросы SQL имеют сложность в , и все проблемы в могут быть выражены как запрос...
В книге Сипсера «Введение в теорию вычислений» на стр. 286 приведено сокращение от 3SAT до задачи о гамильтоновом пути. Есть ли более простое сокращение? Проще говоря, я имею в виду сокращение, которое было бы легче понять (для студентов). Есть ли сокращение, использующее линейное число переменных?...
Я ищу примеры проблемы, которая имеет нижнюю границу ) для входа x .Ω ( | x |2Ω(|x|2\Omega(|x|^2Иксxx Проблема должна иметь следующие свойства: доказательство времени выполнения для любого алгоритма - первым приоритетом должен быть как можно более простой аргумент нижней границы.Ω (...
Требуется ли, чтобы NP-трудная задача была вычислимой? Я так не думаю, но я не
В статье Рамирес-Альфонсон « Сложность проблемы Фробениуса» доказана, что задача NP-полна с использованием редукций Тьюринга. Это возможно? Как именно? Я думал, что это было возможно только за полиномиальное время много одного сокращения. Есть ли какие-либо ссылки по этому поводу? Существуют ли два...
В Алгоритмике Хромковича для сложных задач (2-е издание) есть эта теорема (2.3.3.3, стр. 117): Существует (разрешимая) задача решения такая, что для каждого алгоритма A, который решает P, существует другой алгоритм A ′, который также решает P и дополнительно выполняетпPPAAAпPPA′A′A'PPP...
Моя цель состоит в том, чтобы решить следующую проблему, которую я описал ее вводом и выводом: Входные данные: Направленный ациклический граф с узлами, источниками и стоком ( ).граммграммGммmNNn111m > n ≥ 1м>N≥1m > n \geq 1 Выход: VC-размерность (или приближение к ней) для нейронной сети с...
Для каждой вычислимой функции существует ли задача, которая может быть решена в лучшем случае за время или существует вычислимая функция такая, что любая задача, которая может быть решена в может также быть решено в время?fffΘ(f(n))Θ(f(n))\Theta(f(n))fffO(f(n))O(f(n))O(f(n))o(f(n))o(f(n))o(f(n))...
Я изучаю вычислительную сложность, и мне было интересно, почему проблемы NP-Complete (NPC) вообще являются важным классом. Я нахожу очевидным, почему мы заинтересованы в том, чтобы показать, что данная проблема NP трудна для NP. Я также понимаю определение NPC, и то, что показать конкретное решение...
В матричном умножении Штрассена мы констатируем один странный (по крайней мере для меня) факт, что умножение матрицы на два 2 x 2 требует 7 умножения. Вопрос: Как доказать, что невозможно умножить две матрицы 2 x 2 на 6 умножений? Обратите внимание, что матрицы над целыми...
Учебники повсюду предполагают, что проблема ограниченной почтовой корреспонденции является NP-полной (не более индексов допускается с повторениями). Тем не менее, нигде не показано простого (как, например, то, что может понять студент) полиномиального сокращения времени из другой NP-полной...
Википедия определяет это как Считается, что алгоритм имеет полиномиальное время, если его время выполнения ограничено сверху полиномиальным выражением в размере входных данных для алгоритма, т. Е. для некоторой константы k.T( n ) = O ( nК)T(N)знак равноО(NК)T(n) = O(n^k) Алгоритм работает за сильно...
Благодаря теореме min-cut о максимальном потоке мы знаем, что мы можем использовать любой алгоритм для вычисления максимального потока в сетевом графе для вычисления -min-cut. Следовательно, сложность вычисления минимального -среза не больше, чем сложность вычисления максимального -потока.( с , т...
Как следует из моего предыдущего вопроса , я играл с гипотезой Римана как с рекреационной математикой. В ходе этого процесса я столкнулся с довольно интересным повторением, и мне любопытно, как оно называется, как оно сокращается, и как оно приспосабливается к разрешимости разрыва между простыми...
Теория Экзистенциальная из реалов в PSPACE , но я не знаю , является ли это PSPACE-Complete . Если я считаю, что это не так, как я могу доказать это? В более общем смысле, учитывая проблему в некотором классе сложности X , как я могу показать, что это не X-Complete ? Например, X может быть NP ,...
Я заинтересован в небольшом варианте мозаики: головоломка: каждый край (квадратной) плитки помечен символом из , и две плитки могут быть расположены рядом друг с другом, если символ на лицевой стороне одной плитки равен а символ на лицевой стороне другой плитки равен , для некоторых . Тогда,...
Я прочитал где - то , что наиболее эффективный алгоритм найден можно вычислить факторы в O ( exp( ( 64 / 9 ⋅ б )1 / 3⋅ ( журналb)2/3)O(exp((64/9⋅b)1/3⋅(logb)2/3)O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3}) время, но код я написал это или возможно зависимости от того, насколько быстры деление...
Есть ли какой-нибудь общий метод доказательства проблемы, НЕ являющейся NP-Complete? Я получил этот вопрос на экзамене, который попросил меня показать, является ли какая-то проблема (см. Ниже) NP-Complete. Я не мог придумать никакого реального решения, и просто доказал, что это было в P. Очевидно,...