P против NP и другие ограниченные ресурсами вычисления.
Норберт Блум недавно опубликовал 38-страничное доказательство того, что . Это правильно?п≠ NпP≠NPP \ne NP Также по теме: где еще (в интернете) обсуждается его правильность? Примечание: фокус этого текста вопроса со временем изменился. Смотрите вопрос комментарии для...
Факторинг и изоморфизм графов - это проблемы в NP, которые, как известно, не находятся в P и не являются NP-полными. Каковы некоторые другие (достаточно разные) естественные проблемы, которые разделяют это свойство? Искусственные примеры, полученные непосредственно из доказательства теоремы...
В настоящее время я студент бакалавриата, который должен закончить в этом году. После выпуска я планирую работать в магистратуре / докторантуре TCS. Я начал задаваться вопросом, какие области математики считаются полезными для TCS, особенно (классическая) теория сложности. Какие области вы считаете...
Иногда математики беспокоятся об аксиоме выбора (AC) и аксиоме детерминированности (AD). Аксиома выбора : При любом наборе непустых множеств существует функция F , что, учитывая множество S в C , возвращает элемент из S .СC{\cal C}еffSSSСC{\cal C}SSS Аксиома детерминированности : Пусть - набор...
В настоящее время решается либо полная проблема, либоP S P A C ENPNпNPPSPACЕпSпAСЕPSPACE complete в общем случае невозможно для больших входов. Однако оба они разрешимы в экспоненциальном времени и в полиномиальном пространстве. Поскольку мы не можем создавать недетерминированные или «счастливые»...
Я знаком со многими результатами, в которых используется теорема PCP (главным образом в приближенных алгоритмах), но я никогда не сталкивался с четким объяснением теоремы PCP (то есть, что ).N P = P C P (O(log( н ) ) , O ( 1 ) )Nпзнак равнопСп(О(журнал(N)),О(1))\mathsf{NP} =...
Заданный вопрос состоит в том, является ли следующий вопрос разрешимым: Проблема Учитывая целое число kkk и обещанная машина Тьюринга MMM в P, является ли время выполнения MMM O(nk)O(nk){O}(n^k) относительно длины ввода nnn ? Узкий ответ «да», «нет» или «открытый» является приемлемым (со...
Недавний вопрос по Гека Bennett с просьбой , был ли класс PH содержится в классе РР, получил несколько противоречивые ответы (все это правда, кажется). С одной стороны, несколько результатов оракула были даны наоборот, а с другой Скотт предположил, что ответ, вероятно, положительный, так как...
Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в...
Этот вопрос я задавался вопросом некоторое время. Когда люди описывают проблему P против NP, они часто сравнивают класс NP с творчеством. Они отмечают, что составление симфонии качества Моцарта (аналог задачи NP) кажется намного сложнее, чем проверка того, что уже составленная симфония имеет...
При разработке алгоритма для новой задачи, если я не смогу найти алгоритм полиномиального времени через некоторое время, я мог бы попытаться доказать, что он NP-сложный. Если мне это удастся, я объяснил, почему я не смог найти алгоритм полиномиального времени. Не то, чтобы я точно знал, что P! =...
Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем...
В описательной сложности Иммерман имеет Следствие 7.23. Следующие условия эквивалентны: 1. P = NP. 2. Над конечными упорядоченными структурами FO (LFP) = SO. Это можно рассматривать как «усиление» P = NP до эквивалентного утверждения над (предположительно) классами большей сложности. Обратите...
Это мой первый вопрос на этом сайте. Я учусь в магистратуре по теории вычислений. Как бы вы объяснили проблему P = NP 10-летнему ребенку и почему он получил такое денежное вознаграждение? Твой дубль? Я обновлю вопрос, когда моя голова прояснит...
Существуют некоторые проблемы подсчета, которые включают экспоненциальный подсчет многих вещей (относительно размера входных данных), и в то же время имеют удивительные точные, детерминированные алгоритмы за полиномиальное время. Примеры включают в себя: Подсчет идеальных совпадений в плоском графе...
Предположим, что и G 2 являются двумя неориентированными графами на множестве вершин { 1 , … , n } . Графы изоморфны тогда и только тогда, когда существует перестановка Π такая, что G 1 = Π ( G 2 ) , или более формально, если существует перестановка Π такая, что ( i , j ) является ребром в G 1...
Для (поисковых версий) NP- неполных задач проверить решение явно проще, чем найти его, поскольку проверка может быть выполнена за полиномиальное время, тогда как поиск свидетеля занимает (вероятно) экспоненциальное время. Однако в P решение также может быть найдено за полиномиальное время, поэтому...
Это может быть субъективный вопрос, а не конкретный ответ, но в любом случае. В теории сложности мы изучаем понятие эффективных вычислений. Существуют классы, такие как обозначает полиномиальное время , а обозначает пространство журнала . Оба они считаются своего рода «эффективностью», и они...
Несколько задач оптимизации, которые, как известно, являются NP-сложными на общих графах, тривиально разрешимы за полиномиальное время (некоторые даже за линейное время), когда входной граф является деревом. Примеры включают минимальное покрытие вершин, максимальное независимое множество,...
Теория сложности - мой сильный вторичный интерес, но это не мой основной исследовательский интерес, поэтому у меня нет надежды посетить все конференции, прочитать все блоги и убедиться, что толпа «в» cc: me на каждом кусочке горячие новости. Я пытаюсь сделать что-то из этого, но мне интересно,...