Доказано ли, что квантовые вычисления не лучше в решении полных задач NP, чем классические вычисления, или в это просто
Поскольку целочисленное линейное программирование является NP-полным, существует сокращение Карпа от любой проблемы в NP до него. Я думал, что это подразумевает, что всегда есть формулировка ILP полиномиального размера для любой проблемы в NP. Но я видел статьи по конкретным проблемам NP, где люди...
Планар 3SAT является NP-полным. Планарный экземпляр 3SAT - это экземпляр 3SAT, для которого график, построенный с использованием следующих правил, является плоским: добавить вершину для каждого и ¯ х яxixix_ixi¯xi¯\bar{x_i} добавить вершину для каждого предложения CjCjC_j добавить ребро для каждого...
Если действительно равен , как это улучшит наши алгоритмы, чтобы быстрее вычислять целые числа? Другими словами, какое понимание даст нам этот факт для лучшего понимания целочисленной факторизации?PP{\sf P}NPNP{\sf...
Хорошо известная проблема SAT определена здесь для справки. Проблема DOUBLE-SAT определяется как DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least...
Проблема 3-Перегородка спрашивает , может ли набор из целых чисел может быть разделена на п наборов из трех чисел таким образом, что каждый набор сумм до некоторого заданного целого числа B . Задача сбалансированного разбиения спрашивает, можно ли разбить 2 n целых чисел на два одинаковых набора...
Мой лектор сделал заявление Любая конечная задача не может быть NP-полной В то время он говорил о судоку, который сказал что-то вроде того, что для судоку 8х8 существует ограниченный набор решений, но я не могу точно вспомнить, что он сказал. Я записал записку, которую цитировал, но до сих пор не...
Предположим, в университете есть учебная сессия. У нас есть набор из вопросов и набор из студентов . Каждый студент имеет сомнение в определенной подгруппе вопросов, то есть для каждого студента , пусть множество вопросов , которые студент имеет сомнение. Предположим , что и .Q = { q 1 … q k } n S...
Я читал о NPC и его связи с PSPACE, и я хотел бы знать, могут ли проблемы NPC быть детерминированно решены с использованием алгоритма с наименьшим требованием к полиномиальному пространству, но потенциально с экспоненциальным временем (2 ^ P (n), где P - полиномиальный). Более того, может ли оно...
С точки зрения асимптотического времени выполнения в наихудшем случае, какая NP-полная задача имеет самый известный (точный) алгоритм и что это за алгоритм? Известно ли что-то, что быстрее, чем...
Я пытаюсь решить эту проблему, и я действительно борюсь. Монотонная булева формула представляет собой формулу в логике высказываний , где все литералы являются положительными. Например, (x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor...
Предполагая, что у нас есть задача пpp мы показали, что нижняя граница для решения пpp равна Ω ( 2N)Ω(2n)\mathcal{\Omega}(2^n) . может нижняя граница Ω ( 2N)Ω(2n)\mathcal{\Omega}(2^n) влечет проблему в NпNPNP ?...
Итак, я знаю, что проверка того, является ли обычный язык рRR подмножеством обычного языка SSS , разрешима, поскольку мы можем преобразовать их оба в DFA, вычислить R ∩ S¯R∩S¯R \cap \bar{S} , а затем проверить, является ли этот язык пустым. Однако, поскольку это требует преобразования в DFA,...
Это, наверное, глупый вопрос, но я просто не понимаю. В другом вопросе они придумали теорему Шефера о дихотомии . Мне кажется, это доказывает, что каждая проблема CSP либо в P, либо в NP-полной, но не между ними. Поскольку каждая проблема NP может быть преобразована за полиномиальное время в CSP...
Меняется ли сложность задачи с полной NP-сложностью или NP-полной (как, например, определено здесь ), когда ее вход является унарным, а не двоичным? Какая разница, если вход сильно NP-сложной задачи является унарным? Я имею в виду, если я возьму, к примеру, проблему рюкзака со слабой NP-полной, она...
Я знаю, что максимальное независимое множество на кубических графах без треугольников является NP-полным. Является ли он еще NP-полным, если нам требуется, чтобы независимый набор имел размер точно ?|V|/2|V|/2|V|/2 В основном, ДА экземпляр задачи о независимом множестве в задаче о кубах без...
Мне интересно, есть ли какие-нибудь -hard проблемы, которые являются «полиномиальными» в среднем случае. Я думаю, что есть два способа интерпретировать это?NпNпNP Если , может ли быть алгоритм, решающий задачу N P -hard, с амортизированным (в среднем случае) временем работы O ( n k ) для константы...
Существуют ли какие-либо известные алгоритмы, которые корректно выводят «да» для NP-полной задачи без неявной генерации сертификата? Я понимаю, что легко превратить оракула выполнимости в искатель удовлетворяющих назначений: просто итерируйте по переменным, каждый раз запрашивая оракула...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Я интересно, если есть полиномиальный алгоритм для «2-SAT с XOR-отношений». И 2-SAT, и XOR-SAT находятся в P, но является ли их комбинация? Пример ввода: 2-SAT часть: (a or !b) and (b or c) and (b or d) XOR часть: (a xor b xor c xor 1) and (b xor c xor d) Другими словами, вход представляет собой...