Классы вычислительной сложности и их отношения
Норберт Блум недавно опубликовал 38-страничное доказательство того, что . Это правильно?п≠ NпP≠NPP \ne NP Также по теме: где еще (в интернете) обсуждается его правильность? Примечание: фокус этого текста вопроса со временем изменился. Смотрите вопрос комментарии для...
Этот вопрос я задавался вопросом некоторое время. Когда люди описывают проблему P против NP, они часто сравнивают класс NP с творчеством. Они отмечают, что составление симфонии качества Моцарта (аналог задачи NP) кажется намного сложнее, чем проверка того, что уже составленная симфония имеет...
В описательной сложности Иммерман имеет Следствие 7.23. Следующие условия эквивалентны: 1. P = NP. 2. Над конечными упорядоченными структурами FO (LFP) = SO. Это можно рассматривать как «усиление» P = NP до эквивалентного утверждения над (предположительно) классами большей сложности. Обратите...
Мы знаем, что L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} и что L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , где L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Мы также знаем , что...
Насколько я понимаю, программа теории геометрической сложности пытается разделить , доказав, что постоянство комплексной матрицы гораздо сложнее вычислить, чем определитель.VP≠VNPVP≠VNPVP \neq VNP Вопрос, который у меня возник после просмотра документов GCT: будет ли это сразу означать , или это...
Класс сложности состоит из тех -проблем, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, которая имеет не более одного приемлемого вычислительного пути. То есть решение, если оно есть, является уникальным в этом смысле. Весьма маловероятно, что все -проблемы...
Постоянно растущая сложность компьютерных программ и все более важное положение, которое компьютеры занимают в нашем обществе, заставляют меня задуматься, почему мы до сих пор не используем все вместе языки программирования, на которых вам необходимо предоставить формальное доказательство...
Во введении и объяснении P и NP классы сложности часто даются через машину Тьюринга. Одной из моделей вычислений является лямбда-исчисление. Я понимаю, что все модели вычислений эквивалентны (и если мы можем ввести что-либо в терминах машины Тьюринга, мы можем представить это в терминах любой...
В своей книге «Вычислительная сложность» Пападимитриу пишет: RP в некотором смысле новый и необычный вид сложности класса. Ни одна полиномиально ограниченная недетерминированная машина Тьюринга не может быть основой для определения языка в RP. Чтобы машина N могла определить язык в RP , она должна...
С общей точки смысле зрения, легко поверить , что добавление индетерминизм к значительно расширяет свою власть, т.е. N P гораздо больше , чем P . В конце концов, недетерминизм допускает экспоненциальный параллелизм, который, несомненно, кажется очень мощным. PP\mathsf{P}NPNP\mathsf{NP}PP\mathsf{P}...
Как любитель TCS, я читаю некоторые очень вводные материалы по квантовым вычислениям. Вот несколько элементарных кусочков информации, которые я узнал до сих пор: Известно, что квантовые компьютеры не решают NP-полных задач за полиномиальное время. «Квантовой магии будет недостаточно» (Беннетт и...
Рассмотрим следующую проблему подсчета (или связанную с ней проблему решения): учитывая два натуральных числа, закодированных в двоичном виде, вычислим их наибольший общий делитель (gcd). В каком классе наименьшей сложности содержится эта проблема? Можете ли вы предоставить ссылку? В этом вопросе...
Центральная проблема теории сложности, возможно, против .Н ПпPPNпNPNP Однако, поскольку Природа является квантовой, представляется более естественным рассмотреть классы (т. Е. Задачи решения, решаемые квантовым компьютером за полиномиальное время с вероятностью ошибки не более 1/3 для всех случаев)...
Этот вопрос касается проблем, для которых существует большой открытый разрыв сложности между известной нижней границей и верхней границей, но не из-за открытых проблем самих классов сложности. Чтобы быть более точным, скажем, у проблемы есть классы промежутков A,BA,BA,B (с , не определенным...
В статье «Гипотеза случайного оракула ложна» авторы (Чанг, Чор, Гольдрайх, Хартманис, Хостад, Ранджан и Рохатхи) обсуждают значение гипотезы о случайном оракуле . Они утверждают, что мы очень мало знаем о разделениях между классами сложности, и большинство результатов включают либо использование...
Существует часто цитируемое философское обоснование полагать, что P! = NP даже без доказательств. Другие классы сложности имеют доказательства того, что они различны, потому что если нет, то будут «удивительные» последствия (например, крах полиномиальной иерархии). Мой вопрос: на чем основано...
Вокруг множество проблем с NP-полнотой, и источники их собирают, например, см. Книгу Гэри и Джонсона. Мне было бы интересно увидеть список неполных NEXP задач. Есть ли один доступный? Поскольку я предполагаю, что нет, я открываю этот вопрос (это должна быть вики сообщества? Я не знаю об этом...
Каковы будут неприятные последствия NP = PSPACE? Я удивлен, что ничего не нашел по этому поводу, учитывая, что эти классы являются одними из самых известных. В частности, будет ли это иметь последствия для низших...
Предполагается, что поскольку обратное подразумевает \ mathsf {PH} = \ Sigma_2 . Теорема Ладнера устанавливает, что если \ mathsf {P} \ ne \ mathsf {NP}, то \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset , Однако доказательство, по-видимому, не...
Предположим, что P = NP верно. Будет ли тогда какое-либо практическое применение для построения квантового компьютера, такое как быстрое решение определенных задач, или же любое такое улучшение будет неуместным, основываясь на том факте, что P = NP верно? Как бы вы охарактеризовали повышение...