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

Вопросы о или связанные с P против NP

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

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

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

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

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 , Однако доказательство, по-видимому, не...

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

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

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

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

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

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

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

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

18
Алгоритм, время работы которого зависит от P против NP

Существует ли известный явный пример алгоритма со свойством, состоящим в том, что если то этот алгоритм не выполняется за полиномиальное время, а если то он выполняется за полиномиальное время?п≠ Nпп≠NпP\neq NPп= Nппзнак...

18
Естественный кандидат против гипотезы об изоморфизме?

Знаменитая гипотеза об изоморфизме Бермана и Хартманиса говорит, что все -полные языки полиномиально по времени изоморфны (p-изоморфны) друг другу. Ключевое значение гипотезы является то , что она предполагает P ≠ N P . Она была опубликована в 1977 году, и часть подтверждающих доказательств, что...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

18
Хаос и

Я заинтересован в изучении связей между «хаосом» или, в более широком смысле, динамическими системами и вопросом . Вот пример типа литературы, которую я ищу:п= Nппзнак равноNпP{=}NP Эрчи-Раваш, Мария и Золтан Торошкай. «Твердость оптимизации как переходный хаос в аналоговом подходе к удовлетворению...

18
Список теорем о том, что P не равен NP тогда и только тогда, когда

Я думаю, что было бы неплохо составить список теорем, утверждающих, что P не равен NP, если и только если такие и такие выходы существуют, некоторый класс сложности содержится в другом классе сложности и так далее, и так далее....

16
Подход Гауэрса к «дискретизированной борелевской определенности»

Гауэрс недавно изложил проблему, которую он называет «дискретизированной определенностью Бореля», решение которой связано с доказательством нижних границ схемы. Можете ли вы дать краткое изложение подхода, ориентированного на аудиторию теоретиков сложности? Что потребуется для этого подхода, чтобы...

15
Барьеры для отображения

Мы все знаем, что у есть барьеры. Мы все изучили эти барьеры, потому что мы считаем, что .P ≠ N Pп≠ NпP≠NPP\ne NPп≠ NпP≠NPP\ne NP Однако предположим, что и есть мудрые люди, которые считают, что такая возможность существует . Если это действительно так, то сам факт того, что мы не видели хороших...

13
Каковы естественные примеры нерелятивизируемых доказательств?

Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии). Практически все доказательства кажутся релятивизируемыми. Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству...

12
L / P / PSpace против P / NP

в 1979 году Хопкрофт / Ульман написал, что L ⊆ P ⊆ NP ⊆ PSpace известно, но L ⊊ PSpace является единственным известным (и тривиальным) сдерживанием, известным, хотя все предполагаются как надлежащие сдерживания, и «где вещи все еще стоят» ~ 4 десятилетия спустя , с тех пор существует ли какая-либо...

12
Снижение P против NP до SAT

Следующий вопрос использует идеи из криптографии, примененные к теории сложности. Тем не менее, это чисто теоретический вопрос сложности, и для его ответа не требуется никаких криптовалют. Я намеренно пишу этот вопрос очень неформально. В отсутствие подробностей, это, возможно, указано немного...