Вопросы с тегом «np»

NP означает недетерминированное полиномиальное время.

54
Объясните P = NP проблемы до 10 лет

Это мой первый вопрос на этом сайте. Я учусь в магистратуре по теории вычислений. Как бы вы объяснили проблему P = NP 10-летнему ребенку и почему он получил такое денежное вознаграждение? Твой дубль? Я обновлю вопрос, когда моя голова прояснит...

38
Программа Малмули GCT

Иногда утверждают, что теория геометрической сложности Кетана Малмулей является единственной правдоподобной программой для решения открытых вопросов теории сложности, таких как вопрос P против NP. Было несколько положительных комментариев от известных теоретиков сложности о программе. По словам...

35
NP-полнота решения задачи для обобщенной 15-головоломки

Меня интересует естественное обобщение знаменитой 15-головоломки , где вам нужно сдвигать блоки, пока вы не отсортируете все заданные числа (обычно есть разрыв в 1 блок). Теперь обобщение должно было бы увеличить размер головоломки с 15 до , где одно поле свободно. Я создал небольшую иллюстрацию...

30
Должны ли мы считать

Многие эксперты считают, что гипотеза верна, и используют ее в своих результатах. Меня беспокоит то, что сложность сильно зависит от гипотезы P ≠ N P.PNPP≠NP\mathsf{P} \neq \mathsf{NP}PNPP≠NP\mathsf{P} \neq \mathsf{NP} Итак, мой вопрос: Пока гипотеза не доказана, можно / нужно ли рассматривать ее...

29
Почему так мало естественных кандидатов на NP-промежуточный статус?

Из теоремы Ладнера хорошо известно, что если , то существует бесконечно много N P -интермедиантных ( N P I ) задач. Есть также естественные кандидаты на этот статус, такие как Изоморфизм графов и ряд других, см. Проблемы между P и NPC . Тем не менее, подавляющее большинство в толпе известной н в т...

29
Содержится ли NPI в P / poly?

Предполагается, что поскольку обратное подразумевает \ mathsf {PH} = \ Sigma_2 . Теорема Ладнера устанавливает, что если \ mathsf {P} \ ne \ mathsf {NP}, то \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset , Однако доказательство, по-видимому, не...

28
Естественные NP-полные проблемы с «большими» свидетелями

Вопрос о теории « Что такое NP, ограниченный свидетелями линейного размера? », Задает вопрос о классе NP, ограниченном свидетелями линейного размера , ноO(n)O(n)O(n) Существуют ли естественные NP-полные проблемы, в которых (да) экземпляры размера требуют свидетелей размером больше ?нnnnnnn...

28
Решение проблемы, которая, как известно, не находится в PH, но будет в P, если P = NP

Изменить : Как правильно указал Рави Боппана в своем ответе, и Скотт Ааронсон также добавил еще один пример в своем ответе , ответ на этот вопрос оказался «да» таким образом, которого я вообще не ожидал. Сначала я подумал, что они не ответили на вопрос, который я хотел задать, но, подумав, эти...

27
NP-промежуточные задачи с эффективными квантовыми решениями

Питер Шор показал, что две из наиболее важных NP-промежуточных задач, факторинг и проблема дискретного логарифмирования, находятся в BQP. Напротив, самый известный квантовый алгоритм для SAT (поиск Гровера) дает только квадратичное улучшение по сравнению с классическим алгоритмом, намекая на то,...

27
Причины верить (или нет)

Этот вопрос перенесен из Биржи стеков информатики, потому что на него можно ответить в Теоретической бирже информатики. Мигрировал 6 лет назад . Кажется, что многие люди считают, что , отчасти потому, что они считают, что факторинг не является разрешимым с помощью политикана. (Шива Кинтали...

27
Нетривиальное членство в НП

Есть ли пример языка, который есть в , но где мы не можем доказать этот факт непосредственно, показывая, что существует полиномиальное свидетельство о членстве в этом языке?NпNPNP Вместо этого тот факт, что язык находится в может быть доказан путем сведения его к другому языку в , где связь между...

26
Естественные проблемы в

Существуют ли какие-либо естественные проблемы в , которых нет (как известно / считается, что они есть) в ?U P ∩ c o U PNп∩ c o NпNP∩coNPNP \cap coNPUп∩ c o UпUP∩coUPUP \cap coUP Очевидно, что большая часть, о которой все знают в - это вариант факторинга для решения (не имеет ли коэффициент размера...

25
Самая известная нижняя оценка сложности детерминированного времени для естественной задачи в NP

Это ответ на основные нерешенные проблемы теоретической информатики? Вопрос гласит, что он открыт, если конкретная проблема в NP требует времени .Ω ( n2)Ω(n2)\Omega(n^2) Просмотр комментариев под ответом заставил меня задуматься: Помимо заполнения и подобных уловок, какова наиболее известная нижняя...

25
Доказательства, барьеры и P против NP

Хорошо известно, что любое доказательство, решающее вопрос P против NP, должно преодолевать релятивизацию , естественные доказательства и барьеры алгебраизации . Следующая диаграмма разбивает «пространство доказательств» на различные области. Например, соответствует набору доказательств, которые...

25
Есть ли NP-полный язык, который содержит ровно половину n-битных экземпляров?

Есть ли (желательно натурального) NP-полный язык L⊆{0,1}∗L⊆{0,1}∗L\subseteq \{0,1\}^* , такое , что для любого имеет место ? Другими словами, содержит ровно половину всех битных экземпляров.n≥1n≥1n\geq 1 |L∩{0,1}n|=2n−1|L∩{0,1}n|=2n−1|L\cap...

24
Что такое

Это связано с вопросом: известен ли размер свидетельства для каждого языка NP, уже известного? Некоторые естественные задачи (-complete) имеют свидетелей линейной длины: удовлетворительное назначение для S A T , последовательность вершин для H A M P A T H и т. Д.Н ПNP\mathsf{NP}SА ТSATSATЧАСА МпА...

23
Насколько SAT-оракул поможет ускорить алгоритмы полиномиального времени?

Доступ к оракулу обеспечит значительное, сверхполиномиальное ускорение для всего в (при условии, что набор не пуст). Тем не менее, не совсем ясно, сколько выиграет от этого доступа к оракулу. Конечно, ускорение в не может быть суперполиномиальным, но оно может быть полиномиальным. Например, можем...

22
Утверждения, которые подразумевают

Это своего рода открытый вопрос, за который я заранее прошу прощения. Существуют ли примеры утверждений, которые (казалось бы) не имеют ничего общего со сложностью или машинами Тьюринга, но ответ на них подразумевал бы ?P ≠ N PP≠NP\mathbf{P}\neq...

22
Последствия недоказуемости

Я читал « Является ли P против NP формально независимым? », Но я был озадачен. В теории сложности широко распространено мнение, что . Мой вопрос о том, что, если это не доказуемо (скажем, в ). (Предположим, что мы только узнаем, что не зависит от но никакой дополнительной информации о том, как это...