Ли сглаженный анализ найти свой путь в основной анализ потока алгоритмов? Обычно разработчики алгоритмов применяют сглаженный анализ к своим
Недавно я читал об алгоритмах проверки на сходство и читал, что проблема в P-полноте . Кроме того, следствием этого является то, что эта проблема или любая P-полная проблема вряд ли будут иметь эффективные параллельные алгоритмы. Какая интуиция стоит за этим последним утверждением?...
Я ищу некоторые подсказки в вопросе, заданном моим инструктором. Итак, я только что выяснил, что это решение проблемы :Н Р - с о м п л е т еNP-complete\sf{NP\text{-}complete} На графе есть ли связующее дерево в которое содержит точный набор качестве листьев. Я понял, что мы можем доказать, что это...
Этот вопрос был перенесен из теоретического обмена стеков информатики, поскольку на него можно ответить в обмене стеков информатики. Migrated 7 лет назад . В этой статье в Википедии о проблеме Клика в теории графов вначале говорится, что проблема нахождения клики размера K в графе G является...
Я хотел бы начать с вопроса, говоря, что я программист, и у меня нет большого опыта в теории сложности. Одна вещь, которую я заметил, состоит в том, что, хотя многие проблемы являются NP-полными, когда они распространяются на проблемы оптимизации, некоторые из них гораздо сложнее приблизить, чем...
Предположим , что . N P I - класс задач в N P, которых нет ни в P, ни в N P -твердых. Вы можете найти список проблем предположительно N P I здесь .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Теорема Ладнера говорит нам, что если...
Так что я понимаю идею, что решение проблемы определяется как Есть ли путь P такой, что стоимость ниже, чем C? и вы можете легко проверить это, проверив полученный вами путь. Однако что, если нет пути, который соответствует этим критериям? Как бы вы проверили ответ «нет», не решив проблему TSP с...
Задача подмножества сумм является классической NP-полной задачей: Учитывая список чисел и цель , есть ли подмножество чисел из которое суммирует к ?k L kLLLКkkLLLКkk Студент спросил меня, является ли этот вариант проблемы, называемый проблемой «подмножество продукта», NP-полным: Имея список чисел и...
Одной из возможных причин изучения классов сложности вычислений является понимание возможностей различных видов вычислительных ресурсов (случайность, недетерминизм, квантовые эффекты и т. Д.). Если мы посмотрим на это с этой точки зрения, то кажется, что мы можем получить одну правдоподобную...
Здесь проблема. Даны , где каждый T i ⊆ { 1 , … , n } . Существует ли подмножество S ⊆ { 1 , … , n } с размером не более k таким, что S ∩ T i ≠ ∅ для всех i ? Я пытаюсь свести эту проблему к SAT. Моя идея решения будет иметь переменную х яk,n,T1,…,Tmk,n,T1,…,Tmk, n, T_1, \ldots,...
Это вдохновлено вопросом интервью . Нам дан массив целых чисел и мы должны определить, существуют ли различные i < j < k такие, чтоa1, ... ,Na1,…,ana_1, \dots, a_nя < J < Ki<j<ki \lt j \lt k aК- аJ= аJ- аяak−aj=aj−aia_k - a_j = a_j - a_i k - j = j - ik−j=j−ik - j = j - i т.е....
Как я могу доказать, что преобразование из CNF в DNF является NP-Hard? Я не прошу ответа, просто несколько советов о том, как это
Есть ли в проблемы, в которых рандомизированные алгоритмы бьют нижние оценки для детерминированных алгоритмов? Конкретнее, знаем ли мы для которого ? Здесь \ mathsf {PTIME} (f (n)) означает набор языков, разрешимых рандомизированным TM с постоянной (одной или двухсторонней) ошибкой в f (n) шагах. k...
Может быть, это довольно просто, но у меня есть некоторые проблемы, чтобы получить это сокращение. Я хочу уменьшить Subset Sum до Partition, но в настоящее время я не вижу связи! Можно ли уменьшить эту проблему с помощью редукции Левина? Если не понимаешь, пиши для...
У меня были проблемы с принятием теоретического представления о сложности «эффективно решаемого параллельным алгоритмом», которое задается классом NC : NC - это класс задач, которые могут быть решены параллельным алгоритмом за время на процессорах с .O ( журналсн )O(logcn)O(\log^cn)c , k ∈ Np ( n...
Википедия формулирует проблему суммы подмножеств как поиск подмножества данного мультимножества целых чисел, сумма которого равна нулю. Далее говорится, что это эквивалентно нахождению подмножества с суммой sss для любого заданного sss . Поэтому я считаю, что, поскольку они эквивалентны, должно...
Я столкнулся со следующими сомнениями в сложности Ханойских башен , на которые мне хотелось бы получить ваши комментарии. Это в НП? Попытка ответа: предположим, что Пегги (проверяющий) решает проблему и передает ее Виктору (проверяющему). Виктор может легко увидеть, что окончательное состояние...
Много раз, если сложности имеют константы, такие как 3n, мы пренебрегаем этой константой и говорим O (n), а не O (3n). Я не могу понять, как мы можем пренебречь такими трехкратными изменениями? Некоторые вещи меняются в 3 раза быстрее, чем другие! Почему мы пренебрегаем этим фактом?...
Дискретный логарифм такого же , как нахождение в , дан в , гр и N .bbba c Nab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Интересно, в каких группах сложности (например, для классических и квантовых компьютеров) это находится, и какие подходы (то есть алгоритмы) являются лучшими для выполнения этой задачи....
По словам Иммермана , класс сложности, связанный с запросами SQL, - это в точности класс безопасных запросов в (запросы первого порядка плюс оператор подсчета): SQL захватывает безопасные запросы. (Другими словами, все запросы SQL имеют сложность в , и все проблемы в могут быть выражены как запрос...