Я прочитал несколько раз, что невозможно эффективно перевернуть ответ NDTM. Однако я не понимаю, почему. Например, учитывая NDTM который выполняется в , этот текст (раздел 3.3) утверждает, что неясно, как другой NDTM может определить за время, как перевернуть...
Мне интересно, есть ли какие-нибудь -hard проблемы, которые являются «полиномиальными» в среднем случае. Я думаю, что есть два способа интерпретировать это?NпNпNP Если , может ли быть алгоритм, решающий задачу N P -hard, с амортизированным (в среднем случае) временем работы O ( n k ) для константы...
Пусть будет некоторой проблемой подсчета, которая известна как # P -Complete .ΠΠ\PiPPP Означает ли это , что является P X -Жесткий (т.е. не PTAS для проблема существует , если P = N P...
Является ли проблема определения того, является ли данное булево выражение выполнимым в вычислительном отношении отличным от фактического нахождения решения выражения? Другими словами, есть ли другой способ найти, что данное выражение выполнимо без явного определения «правильных настроек» для...
Все знают «Garey & Johnson», и я всегда обращаюсь к ним, когда мне нужно выполнить преобразование для доказательства NP-твердости. Однако недавно я нуждался в доказательстве твердости APX, и мне интересно, есть ли подобный (и более современный ...?) Набор проблем, которые, как было показано,...
Существуют ли какие-либо известные алгоритмы, которые корректно выводят «да» для NP-полной задачи без неявной генерации сертификата? Я понимаю, что легко превратить оракула выполнимости в искатель удовлетворяющих назначений: просто итерируйте по переменным, каждый раз запрашивая оракула...
Я знаю, что это глупо, но мне удалось запутаться, и мне нужна помощь, чтобы решить эту проблему Предположим, что , тогда ясно, что для каждого оракула имеем что противоречит тому, что существует некоторый оракул для которого , следовательно,P=NPP=NPP=NPAAAPA=NPAPA=NPAP^A=NP^AAAAPA≠NPAPA≠NPAP^A\neq...
Зоопарк Сложности определяет как класс задач решения, решаемых детерминированной машиной Тьюринга за линейное время.LINLINLIN LIN⊆PLIN⊆PLIN \subseteq P Поскольку HORN-SAT разрешим в (как указано в алгоритмах линейного времени для проверки выполнимости формул рогового высказывания (1984)...
Я пытаюсь разработать задание (взятое из книги « Алгоритмы» С. Дасгупты, К. Х. Пападимитриу и У. В. Вазирани , глава 8, проблема 8.6а), и я перефразирую то, что в нем говорится: Учитывая, что 3SAT остается NP-завершенным, даже если он ограничен формулами, в которых каждый литерал появляется не...
Альтернативная формулировка Я придумал альтернативную формулировку нижеприведенной проблемы. Альтернативная формулировка на самом деле является частным случаем проблемы ниже и использует двудольные графы для описания проблемы. Тем не менее, я считаю, что альтернативная формулировка все еще...
У меня проблема в голове, я думаю, что это проблема NPC, но я не знаю, как это доказать. Вот проблема: В очень большом озере k островов и n понтонов в форме вееров. Эти понтоны имеют одинаковый размер, но имеют разные начальные направления и находятся в разных первоначальных положениях в озере....
Я изучал ранговый коэффициент корреляции Спирмена ρ = ∑я( хя- х¯) ( уя- у¯)Σя( хя- х¯)2Σя( уя- у¯)2-------------------√ρзнак равноΣя(Икся-Икс¯)(Yя-Y¯)Σя(Икся-Икс¯)2Σя(Yя-Y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} ....
Сегодня я узнал, что алгоритм анализа отличается в зависимости от вычислительной модели. Это то, о чем я никогда не думал и не слышал. Пример, данный мне, который проиллюстрировал это далее, пользователем @chi был: Например, рассмотрим задачу: дано вернуть . В оперативной памяти это может быть...
Я беру курс по вычислительной сложности. Моя проблема в том, что я не понимаю метод релятивизации . К сожалению, во многих учебниках я пытался найти немного интуиции, но пока безуспешно. Буду признателен, если кто-нибудь сможет пролить свет на эту тему, чтобы я смог продолжить сам. Несколько...
Рассмотрим следующую проблему, входной экземпляр которой представляет собой простой граф и натуральное целое число k .гGGКkk Существует ли множество такое, что G - S двудольный и | S | ≤ к ?S⊆ V( G )S⊆V(G)S \subseteq V(G)G - SG−SG - S| S| ≤k|S|≤k|S| \leq k Я хотел бы показать, что эта проблема...
Отказ от ответственности: я знаю, что есть похожие вопросы уже здесь и на Stackoverflow. Но они все о столкновениях, о которых я не прошу. Мой вопрос: почему столкновительный меньше LookUp O(1)в первую очередь? Давайте предположим, что у меня есть эта хеш-таблица: Hash Content ------------- ghdjg...
Учитывая два целых числа и в двоичном представлении, какова сложность вычисления размера битов ?н х нxИксxnNnxnИксNx^n Один из способов сделать это - вычислить путем вычисления аппроксимации с достаточной точностью. Похоже, что вычисление с битами точности может быть выполнено в где - время,...
Существует классическая игра-головоломка, очень похожая на кроссворд, за исключением того, что дается список слов, а затем дается квадратная доска составленная из единичных квадратов, с некоторыми квадратами, затемненными как кроссворд , и на некоторых квадратах уже написано письмо. Цель состоит в...
Типичные примеры NP-сложных задач (клика, 3-SAT, покрытие вершин и т. Д.) Относятся к тому типу, когда мы не знаем, является ли ответ «да» или «нет» заранее. Предположим, что у нас есть проблема, в которой мы знаем ответ «да», кроме того, мы можем проверить свидетеля за полиномиальное время. Можем...
Относительно потока, Доказывающего, что преобразование из CNF в DNF является NP-Hard (и связанный математический поток ): Как насчет другого направления, от DNF до CNF? Это легко или сложно? На странице 2 этой статьи они, похоже, намекают на то, что оба направления одинаково трудны, когда говорят:...