|
Архивы |
---|
1 |
Эта статья должна быть исправлена !!! (NP-Complete не является классом сложности)
Эта статья шокирует своим плохим стилем, что делает ее почти непонятной для любого англоговорящего человека. - Предыдущий беззнаковый комментарий добавлен 130.220.239.128 ( обсуждение ) 01:49, 10 декабря 2013 г. (UTC)
- Насколько я могу судить, большинство предложений ясны и лаконичны, и всегда используется соответствующий словарь (для предмета). Почти все предложения написаны активным голосом, поэтому я не вижу ни одного излишне длинного. MrFreddy7 ( разговорное ) 21:50, 8 мая 2019 г. (UTC)
Основная проблема статьи - неверное предположение, что «NP-полный» - это класс сложности. Очевидно, что «NP-полный» - это прилагательное для описания класса NP-полных задач. Идея о том, что NP-complete является классом, ниже поддерживается только одним пользователем Википедии ( Deco ) (и, возможно, некоторыми неавторизованными источниками, такими как учебники по алгоритмам). Во всех статьях и учебниках по теории сложности NP-complete используется как прилагательное, и я (как теоретик-компьютерщик) никогда не видел, чтобы NP-complete использовалось как имя класса сложности (NPC можно определить как класс NP-полных задач. , но это «NPC», а не «NP-complete»). Эта давняя проблема должна быть исправлена в этой статье. Я знаю о предыдущей попытке исправить эту статью, но некоторые силы природы отменили эти исправления.
Пожалуйста, обсудите это, чтобы завершить эту нелепую проблему этой статьей, если действительно есть что обсудить. - Предыдущий беззнаковый комментарий добавлен 130.233.179.227 ( обсуждение ) 08:02, 13 ноября 2013 г. (UTC)
- Я согласен с этой точкой зрения и соответствующим образом перефразирую введение. Пинточ ( разговорное ) 20:49, 20 июля 2014 (UTC)
Проблема суммы подмножества
«Никто не знает значительно более быстрого способа решить проблему, чем попробовать каждое возможное подмножество, что очень медленно». Я вырезал это. На самом деле существует более быстрый способ решить эту проблему, который можно найти на связанной странице. Это неэффективно, но намного лучше, чем пробовать все комбинации. —Предыдущий комментарий без подписи, добавленный 86.144.186.205 ( обсуждение ) 17:26, 26 августа 2007 г. (UTC)
- Вопрос в том, действительно ли это значительно быстрее. Урезание этого также заставляет думать, что мы точно знаем, что нет эффективного алгоритма. - Mellum 21:44, 26 августа 2007 г. (UTC)
Да, это на много миль быстрее. Испытание каждого возможного подмножества занимает O (2 n N) времени. Можно решить проблему за время O (2 n / 2 N) самым быстрым методом. Метод описан под заголовком «Алгоритм экспоненциального времени» на странице задачи суммы подмножества . Глупо возвращать это утверждение, когда оно опровергнуто на другой странице - предыдущий комментарий без подписи, добавленный 86.156.53.169 ( обсуждение ) 20:50, 27 августа 2007 г. (UTC)
- Полагаю, это просто разница в толковании термина «существенно». Достаточно сказать, что алгоритм с полиномиальным временем неизвестен. Dcoetzee 00:02, 28 августа 2007 г. (UTC)
Я работал с предположением, что кто-то действительно может попытаться реализовать метод в коде. На практике разница в скорости будет огромной, и программист захочет об этом знать.
Я хотел бы предложить, чтобы первый пример был основан на задаче коммивояжера. На мой взгляд, это гораздо легче понять обычному человеку, не связанному с теорией сложности, как практический пример. Кроме того, где у нас есть указатели на статистическую физику, термодинамику и самоорганизующиеся системы? Это кажется существенным упущением. —Предыдущий комментарий без подписи, добавленный 86.156.53.247 ( обсуждение ) 21:59, 28 августа 2007 г. (UTC) 75.211.0.29 ( обсуждение ) 18:58, 16 мая 2008 г. (UTC)
Точность
Мне не нравится слово «вероятно» в этом контексте. Либо что-то находится в P, либо нет. Мы просто еще не знаем, какой именно. Что мы действительно знаем, так это то, что если какая-либо NP-сложная проблема находится в P, то все NP-проблемы находятся в P.
Лоуренс Д'Анна
Кажется, на этой странице есть противоречия. Сначала говорится, что «NP-полные проблемы - это самые сложные проблемы в NP», а затем говорится: «Не совсем правильно говорить, что NP-полные проблемы являются самыми сложными проблемами в NP». Я не обновлял страницу, потому что я не эксперт в этом, но не мог бы кто-нибудь исправить этот запутанный бит?
Спасибо,
Родриго де Сальво Браз
«Не совсем правильно говорить, что NP-полные проблемы являются самыми сложными проблемами в NP. Если предположить, что P и NP не равны, гарантированно будет бесконечное количество проблем, которые находятся в NP, но не являются ни NP- Complete, ни в P. Некоторые из этих задач могут иметь более высокую сложность, чем некоторые из NP-полных задач ".
Я слышал о фазовых переходах в NP-полных задачах. Как узнать, что если P не равно NP, то есть задачи, которые находятся в NP, но не в P или NP-полных?
Спасибо
Дэвид Бернье
Подробное объяснение можно найти на страницах 154–155 книги Гэри и Джонсон. Из теоремы Ладнера 1975 года следует, что если P не равно NP, то для каждой NP-полной задачи существует подзадача, которая может быть распознана за полиномиальное время, которая не является ни NP-полной, ни в P. Dominus 21:22 14 марта 2003 г. (UTC)
NP-полные - это самые сложные проблемы в NP по определению (проблема является NP-полной, если она принадлежит NP, и ее можно использовать для решения любой NP-проблемы посредством полиномиального сокращения времени). Кук доказал, что SAT является NP-завершенной. Было доказано, что другие проблемы являются NP-завершенными, решая с их помощью задачу SAT. Ян Дэвид Мол 12:10 2 июня 2003 г. (UTC)
Может быть, было бы неплохо заменить «проблемы» в первой строке (или даже во всем) на «проблемы решения»? См. Страницу в Википедии о NP-эквиваленте по моей причине. Леон Планкен 22:29 19 июня 2003 г. (UTC)
Привет, это означает субэкспоненциальное время для NP-полной задачи? я не могу найти рукопись, но я видел ее где-то цитируемым. кто-нибудь знает / читал рукопись? В. Д. Смит. Нахождение оптимального тура коммивояжера N-городов на евклидовой плоскости в субэкспоненциальном времени и полиномиальном пространстве. Рукопись, 1988. 68.121.211.14 01:51, 21 апреля 2005 г. (UTC)
- Насколько мне известно, планарная задача TSP не является NP-полной. Я не верю, что существует какой-либо субэкспоненциальный алгоритм для NP-полной проблемы (если не считается что-то вроде O (2 ^ n / log n)). Деку 06:13, 21 апр 2005 (UTC)
плоская чайная ложка определенно является NP полной из-за сокращения из плоского цикла ветчины 68.121.211.14 19:15, 21 апреля 2005 г. (UTC)
- Ой, ладно. Вы правы, в любом случае так безопаснее (кто знает, что люди найдут). Деку 05:42, 22 апр 2005 (UTC)
- Поправьте меня, если я ошибаюсь, но планарный гамильтонов цикл - это проблема нахождения гамильтонова цикла в плоском графе, то есть в графе, который не имеет пересекающихся ребер при рисовании на плоскости. Планарный TSP - это проблема поиска цикла TSP с минимальной стоимостью для точек на плоскости, т. Е. Связанный граф заполнен ребрами между каждой парой точек, а расстояния - это евклидовы расстояния между точками. Я не вижу простого перехода от плоского гамильтонова цикла к планарному ЗК. 27 апреля 2005 г.
Цитирование статьи:
"В теории сложности NP-полные проблемы являются самыми сложными проблемами в NP в том смысле, что они, скорее всего, не будут в P. Причина в том, что если бы вы могли найти способ решить NP-полную проблема быстро, тогда вы могли бы использовать этот алгоритм для быстрого решения всех проблем NP ".
Я понимаю, что проблема здесь не в том, насколько «быстро» алгоритм может решить данную проблему, а в том, что вы можете рассчитать время, которое потребуется алгоритму для решения проблемы.
Карлос Бадиола
НПИ
Я вырезал этот абзац:
- «Не совсем правильно говорить, что NP-полные проблемы являются самыми сложными проблемами в NP. Если предположить, что P и NP не равны, гарантированно будет бесконечное количество проблем, которые находятся в NP, но не являются ни NP- Complete, ни в P. Некоторые из этих задач могут иметь более высокую сложность, чем некоторые из NP-полных задач ".
Хотя P ≠ NP подразумевает, что NPI = NP-NPC-P непусто, проблемы в NPI могут быть сведены к проблемам в NPC, тогда как проблемы в NPC не могут быть сведены к проблемам в NPI. Кажется разумным описать такое положение вещей как «проблемы в NPC сложнее, чем проблемы в NPI». Так что абзац вводит в заблуждение.
Обсуждение NPI, вероятно, где-то должно быть. Gdr 21:40, 2004 21 июля (UTC)
Несовершенные решения - приближение
Аппроксимация: алгоритм, который быстро находит неоптимальное решение, которое находится в пределахопределенный (часто известный) диапазон оптимального. Не все NP-полные задачи имеютхорошие алгоритмы аппроксимации, а для некоторых задач поиска хорошего алгоритма приближения достаточно, чтобы решить саму задачу .
В абзаце выше я не понимаю выделенную жирным шрифтом фразу. Кто-нибудь может объяснить? - Сундар 07:26, 25 ноября 2004 г. (UTC)
- Я тоже этого не понимаю. Я предполагаю, что имеется в виду, что хорошее приближение некоторых проблем является NP-трудным и, по сути, не проще, чем их точное решение. Я просто удалю его, так как другие подходы также не имеют в списке своих «предостережений».
Неоптимальность
Привыкнув к понятию оптимальности по отношению только к производительности, мне и в голову не пришло, что его можно правильно использовать (в параграфе «Алгоритмы приближения»). Может быть, это потому, что я не являюсь носителем английского языка. Может ли кто-нибудь его переформулировать, чтобы пояснить, что речь идет о правильности ? - Сундар 08:33, 3 февраля 2005 г. (UTC)
NP-жесткий
Под «формальным определением ...», последним абзацем о «NP-сложном», говорится: «Например, выбрать идеальный ход в некоторых настольных играх на произвольно большой доске (неформально)» строго сложнее, чем «любая задача NP. "
Разве это не должно быть «по крайней мере так же сложно, как любая проблема NP», а не «строго сложнее, чем»? Например, Garey and Johnson, стр. 109 (первая страница главы 5), говорит, что «по крайней мере так же сложно, как NP-полные задачи». - Bubba73 00:23, 25 мая 2005 г. (UTC)
- Что касается большинства игр, вы правы в том, что «по крайней мере так сложно» - это все, что мы можем сказать на данный момент. Некоторые формы Go являются EXP-полными, поэтому его нельзя решить в P, но все же можно решить в NP (хотя, вероятно, нет). Я предполагаю, что могут существовать игры, которые находятся строго за пределами NP, но я не знаком с ними. Деку 23:54, 24 мая 2005 г. (UTC)
- Этот абзац, вероятно, нуждается в уточнении. NP-hard означает «по крайней мере так же сложно, как», но некоторые проблемы «строго сложнее». - Bubba73 00:23, 25 мая 2005 г. (UTC)
Эта проблема NP-полная?
Я обнаружил эту проблему и задался вопросом, является ли она NP-завершенной: у вас есть куча задач, которые занимают разное количество времени, и некоторые задачи нельзя запустить, пока другие задачи не будут завершены. У вас неограниченные ресурсы, вы можете выполнять разные задачи параллельно и пытаетесь найти кратчайшее время для выполнения всех задач.
- Я предполагаю, что вы не пытаетесь заставить нас делать за вас домашнее задание. То, что вы описываете, по сути является проблемой планирования , также называемой заданием или последовательностью задач, и было одной из 21 NP-завершенных проблем Карпа . Он показал ее NP-полную редукцией из задачи о ранце . Описанный вами граф называется графом зависимостей задач. Технически, конкретная проблема, которую вы описываете, на самом деле является NP-сложной (она не является NP-полной, потому что это даже не проблема решения). Деку 05:24, 19 июня 2005 г. (UTC)
Спасибо! - SurrealWarrior 18:43, 20 июня 2005 г. (UTC)
Доказательства
Почему у нас нет доказательств np-полноты в Википедии? На многих страницах с отдельными проблемами я замечаю, что там может упоминаться вид сокращения, но он никогда не вдавался в подробности ... Есть ли для этого причина? - Авериск, 08:48, 12 декабря 2005 г. (UTC)
- На самом деле мы делаем. Обычно мы описываем доказательства в статьях, связанных с конкретными теоремами, такими как теорема Кука . Большинство сокращений NP достаточно просты, хотя нет причин, по которым мы не могли бы включить их в статьи о проблемах (или, по крайней мере, в набросок доказательства). Одна проблема, однако, заключается в том, что книги обычно представляют сокращения в определенном порядке, чтобы не полагаться на круговые рассуждения, например, сводя две проблемы друг к другу - это сложнее в нашей плоской, взаимосвязанной организации статей. Деку 09:02, 12 декабря 2005 г. (UTC)
- Вау, быстрый ответ. Да, я понимаю, о чем вы. Может быть, мы могли бы сделать отдельные страницы для корректур и следовать определенному порядку, как вы сказали? - Авериск, 09:14, 12 декабря 2005 г. (UTC)
Задача коммивояжера не является NP-полной
Статья довольно небрежная: в ней неоднократно утверждается, что задача коммивояжера NP-полна. Это не так: TSP - это функциональная проблема, и только проблемы решения могут быть NP-полными. (TSP является полным для FP NP .) Конечно, существует NP-полная версия TSP с решением (существует ли тур с общим весом < k ?) С учетом взвешенного графа и границы k . Но люди обычно имеют в виду не это, когда говорят «TSP»: они хотят знать настоящий тур!
Аналогичные проблемы существуют и с некоторыми из других упомянутых проблем (например, в пути Гамильтона нам обычно нужен путь, в логической выполнимости мы хотим удовлетворительного назначения и т. Д. Я внес одно изменение, чтобы помочь с этим, но для этого требуется дополнительная работа . Многие авторы принимают конвенцию использовать все-колпачки для решения проблем ( при этом "Гамильтоне путь" против HAMILTON PATH ). Gdr 21:59, 6 января 2006 (UTC)
- Я согласен с тем, что мы должны быть точными, но довольно часто, особенно на неформальных форумах, говорят о функциональной проблеме, когда на самом деле речь идет о проблеме решения. Кто-то может возразить, что «проблема коммивояжера» - неоднозначный термин, который может относиться к любой версии. Однако, если мы хотим быть точными, давайте примем соглашение, которое избегает раздражающего многословия, такого как та вещь, которую вы описываете только заглавными буквами. Деку 22:09, 6 января 2006 г. (UTC)
Я нашел использование TSP в качестве примера очень запутанным. Мне кажется, что он далек от того, чтобы быть "дружественным" или "доступным", очевидно, противоречит вашим определениям того, что означает NP-полнота. Очевидно, что результат TSP так же сложно проверить, как и вычислить, поскольку вам нужно хотя бы частично вычислить все другие маршруты, чтобы доказать, что нет более короткого маршрута. Это не относится к версии решения, которую легко проверить согласно вашему определению. Если бы TSP был в NPC, как определено выше, тогда это доказывало бы, что P = NP, не так ли? Использование этого примера сбило меня с толку, когда я прочитал статью. [Роб: август 2010] —Предыдущий неподписанный комментарий добавлен 86.168.27.244 ( обсуждение ) 08:15, 13 августа 2010 г. (UTC)
- да, но насколько я понимаю, вы частично вычисляете все остальные маршруты, чтобы доказать, что они длиннее (я думаю, заменяя подмножества сегментов), и делаете это за полиномиальное время. Это может быть большой расчет, но рост расчета по отношению к N имеет известную границу, которая меньше, чем рост сложности поиска решения, которое вы тестируете. 207.237.159.111 ( разговорное ) 15:58, 11 апреля 2012 (UTC)
Произвольная награда
Я удалил следующее утверждение:
- Никто еще не смог доказать, действительно ли NP-полные проблемы разрешимы за полиномиальное время, что делает эту проблему одной из величайших нерешенных проблем математики. Институт математики Клэя в Кембридже, Массачусетс, предлагает вознаграждение в размере 1 миллиона долларов любому, у кого есть формальное доказательство того, что P = NP или что P ≠ NP.
Ясно, что это вандализм со стороны какого-то шутника, который думает, что было бы забавно выпрыгнуть из ванны обнаженным и вопить Эврика! когда они находят тривиальное решение P ≠ NP. 59.112.43.12 10:15, 4 октября 2006 г. (UTC)
Нет, это правда, даже если P = NP опровергнуть невозможно. Сейчас восстановлен. (Woops, SAT основан на размере ввода, а не на количестве литералов.) Давилла 17:09, 4 октября 2006 г. (UTC)
Да, и CMI предлагает вознаграждение в размере 1 миллиона долларов. Это проблема Премии тысячелетия. Деку 21:46, 4 октября 2006 г. (UTC)
Я доказал несколько лет назад, и проблема в журналах и в том факте, что теорема Кука неверна: http://www.archive.org/search.php?query=%22Juan%20Manuel%20Dato%22 —Preceding неподписанный комментарий добавлен 79.109.168.68 ( обсуждение ) 11:59, 7 марта 2011 г. (UTC)
Так что пространство не имеет значения ???
Мои правки были отменены . Извините, вы не можете оспорить Space-time_tradeoff . В пространстве вопросов P = NP не имеет значения. Если бы пространство не принималось во внимание, я бы получил Нобелевскую премию по математике, поскольку в своем домашнем задании я уже доказал, что *** ВСЕ *** задачи класса NP могут быть решены за полиномиальное время, следовательно, P = NP (если вы ПОЛНОСТЬЮ игнорируете соображения относительно места).
Вот пример доказательства: начните с использования вычислений ДНК / (экспоненциального воспроизводства культур клеток), чтобы сгенерировать 2 ^ N входных строк за время N. Затем используйте алгоритм ранжирования списка, который реализует переход указателя, чтобы он мог присвоить уникальное значение для все 2 ^ N входов за время N. Затем, используя генетически модифицированную культуру клеток, создайте 2 ^ N компьютеров ДНК за время N, чтобы проверить все 2 ^ N входов не более чем за время и пространство тета (n ^ k) (также известное как поли время и пространство) параллельно, единственная оставшаяся входная строка - это удовлетворительный ответ. Поскольку все алгоритмы класса NP должны выполняться в полиномиальное время и пространство, использование вышеуказанного метода может решить все проблемы NP за полиномиальное время, но ТОЛЬКО с экспоненциальным компромиссом в пространстве. Это очень простое приложение массового параллелизма. Поскольку я только что проявил себя, не буду ждать, чтобы поправить статью. Если вы хотите (или хотите) отменить его, опубликуйте свои причины здесь. Я должен указать, что я никоим образом не являюсь экспертом по этой теме, но я должен также указать, что моя вышеупомянутая логика была одобрена моим профессором, который зарабатывает себе на жизнь этой темой. - АНОНИМНЫЙ COWARD0xC0DE 07:35, 1 декабря 2006 г. (UTC)
- Я не знаком с предметом обсуждения, но, пожалуйста, ознакомьтесь с основными политиками в отношении содержания, включая проверяемость и отсутствие оригинальных исследований . Если эта идея была опубликована в другом месте, пожалуйста , процитировать в надежной публикации для резервного копирования изменений. Я полагаю, это то, что могут сказать другие редакторы, более знакомые с этим вопросом. Спасибо за ваше время. Луна Сантин 07:37, 1 декабря 2006 г. (UTC)
На первый взгляд, оба примера создают впечатление, что теперь у нас есть эффективное решение больших экземпляров NP-полных задач как полиномиальных нужно время. Но очень важно учитывать, что экспоненциальная сложность не была устранена, но только время от времени космос. [1]
Другие приложения включают в себя атаку на правительственную схему шифрования DES. использование молекулярных компьютеров, решение проблемы выполнимости и использование ДНК множить целые числа. [2]
- Однако оба они ссылаются на одну и ту же работу доктора Леонарда Адлемана, который смог решить пример задачи гамильтонова пути с помощью вычислений ДНК. - АНОНИМНЫЙ COWARD0xC0DE 05:41, 23 декабря 2006 г. (UTC)
- NP определяется с использованием конкретной модели машины, а именно недетерминированных машин Тьюринга. На недетерминированных машинах Тьюринга полиномиальное время подразумевает полиномиальное пространство. Ваше «доказательство» не использует недетерминированные машины Тьюринга и, следовательно, не применимо к NP. - Mellum 08:03, 1 декабря 2006 г. (UTC)
- я говорю о
Следствием этого определения является то, что если бы у нас был алгоритм с полиномиальным временем для C мы могли бы решить все задачи в NP за полиномиальное время.
- и я также говорю, что все проблемы в NP могут быть решены за полиномиальное время (это может занять все пространство известной вселенной, но это все еще может быть решено за полиномиальное время). Я могу (теоретически) построить машину для решения всех задач класса NP за полиномиальное время, которая применяется к NP и делает излишним приведенное выше утверждение. Да, недетерминированные токарные станки являются неотъемлемой частью обсуждения NP, но это не означает, что массово-параллельные детерминированные алгоритмы следует игнорировать при обсуждении np-полноты. - АНОНИМНЫЙ COWARD0xC0DE 05:41, 23 декабря 2006 г. (UTC)
- Что означает «относится к НП»? Если это означает, что любую программу для вашей машины можно преобразовать в программу для недетерминированной машины Тьюринга только с полиномиальным замедлением, вы бы решили проблему P vs. NP (что кажется маловероятным); в противном случае ваше утверждение не имеет значения. - Mellum 20:21, 28 декабря 2006 г. (UTC)
- Вы сказали, что мое «доказательство» неприменимо к НП. Я категорически не согласен; У меня есть машина, которая может решать все проблемы класса NP за полиномиальное время (см. Мои процитированные ссылки или мое доказательство для примера), поэтому эту машину можно рассматривать при обсуждении проблем класса NP. Я НЕ говорю о недетерминированной машине Тьюринга, я говорю о массивно-параллельной детерминированной машине Тьюринга (но я не говорю о простом суперкомпьютере с тысячами процессоров, я говорю о ДНК-компьютере с миллиардами «процессоров» или чем-то еще. вы хотите это назвать). Я не делаю никаких заявлений о P = NP или о том, что P является строгим подмножеством NP. Я только говорю, что все задачи класса NP могут быть вычислены за полиномиальное время за счет дополнительной сложности пространства. Это почти дословно то, что я уже получил: «Но очень важно учитывать, что экспоненциальная сложность не была устранена, а только перенесена из времени в пространство». Итак, после того, как вы перенесете его из времени в пространство, вы теперь должны задать вопрос P vs. NP относительно пространства. Итак, в конце концов, вопрос P vs. NP касается параллельной «работы» = (время × пространство или время × (количество процессоров)). Утверждение статьи «Следствием этого определения является то, что если бы у нас был алгоритм с полиномиальным временем для C , мы могли бы решить все проблемы в NP за полиномиальное время». является чрезвычайно избыточным, поскольку все проблемы класса NP могут быть решены за полиномиальное время. Люди в Complexity_classes_P_and_NP приняли мою правку: «По сути, вопрос P = NP спрашивает: если положительные решения проблемы ДА / НЕТ могут быть быстро проверены за полиномиальное время, можно ли быстро вычислить ответы за полиномиальное время и пространство?» , потому что без учета сложности пространства все обсуждение становится излишним, потому что все проблемы класса NP могут быть решены за полиномиальное время. - АНОНИМНЫЙ COWARD0xC0DE 04:55, 30 декабря 2006 г. (UTC)
- Термин «полиномиальное время» должен относиться к конкретной модели машины, иначе он не имеет смысла. В этом контексте это относится к детерминированным машинам Тьюринга. Если вы разрешаете другие машины, вы также можете взять машину оракула NP и заявить, что все в NP может быть решено за постоянное время. Но это всего лишь перестановка стоек ворот, не имеющая отношения к рассматриваемому вопросу. Поэтому, пожалуйста, больше не добавляйте свои правки. - Mellum 11:57, 30 декабря 2006 г. (UTC)
- Я согласен. Вы предполагаете, что предложение подразумевает контекст детерминированных машин Тьюринга, однако эта ключевая фраза явно нигде в этом предложении не указана. Я никогда не думал жаловаться на этом основании. «Алгоритм», упомянутый в предложении, может быть легко предназначен для недетерминированной машины Тьюринга, и в предложении нет таких ограничений. Итак, теперь мне остается только поспорить, являются ли параллельные вычисления детерминированными или нет. Просто ответьте на это в другом моем сообщении (ветке) ниже, если хотите. - АНОНИМНЫЙ COWARD0xC0DE 12:18, 2 января 2007 г. (UTC)
- Термин «полиномиальное время» должен относиться к конкретной модели машины, иначе он не имеет смысла. В этом контексте это относится к детерминированным машинам Тьюринга. Если вы разрешаете другие машины, вы также можете взять машину оракула NP и заявить, что все в NP может быть решено за постоянное время. Но это всего лишь перестановка стоек ворот, не имеющая отношения к рассматриваемому вопросу. Поэтому, пожалуйста, больше не добавляйте свои правки. - Mellum 11:57, 30 декабря 2006 г. (UTC)
- Вы сказали, что мое «доказательство» неприменимо к НП. Я категорически не согласен; У меня есть машина, которая может решать все проблемы класса NP за полиномиальное время (см. Мои процитированные ссылки или мое доказательство для примера), поэтому эту машину можно рассматривать при обсуждении проблем класса NP. Я НЕ говорю о недетерминированной машине Тьюринга, я говорю о массивно-параллельной детерминированной машине Тьюринга (но я не говорю о простом суперкомпьютере с тысячами процессоров, я говорю о ДНК-компьютере с миллиардами «процессоров» или чем-то еще. вы хотите это назвать). Я не делаю никаких заявлений о P = NP или о том, что P является строгим подмножеством NP. Я только говорю, что все задачи класса NP могут быть вычислены за полиномиальное время за счет дополнительной сложности пространства. Это почти дословно то, что я уже получил: «Но очень важно учитывать, что экспоненциальная сложность не была устранена, а только перенесена из времени в пространство». Итак, после того, как вы перенесете его из времени в пространство, вы теперь должны задать вопрос P vs. NP относительно пространства. Итак, в конце концов, вопрос P vs. NP касается параллельной «работы» = (время × пространство или время × (количество процессоров)). Утверждение статьи «Следствием этого определения является то, что если бы у нас был алгоритм с полиномиальным временем для C , мы могли бы решить все проблемы в NP за полиномиальное время». является чрезвычайно избыточным, поскольку все проблемы класса NP могут быть решены за полиномиальное время. Люди в Complexity_classes_P_and_NP приняли мою правку: «По сути, вопрос P = NP спрашивает: если положительные решения проблемы ДА / НЕТ могут быть быстро проверены за полиномиальное время, можно ли быстро вычислить ответы за полиномиальное время и пространство?» , потому что без учета сложности пространства все обсуждение становится излишним, потому что все проблемы класса NP могут быть решены за полиномиальное время. - АНОНИМНЫЙ COWARD0xC0DE 04:55, 30 декабря 2006 г. (UTC)
- Что означает «относится к НП»? Если это означает, что любую программу для вашей машины можно преобразовать в программу для недетерминированной машины Тьюринга только с полиномиальным замедлением, вы бы решили проблему P vs. NP (что кажется маловероятным); в противном случае ваше утверждение не имеет значения. - Mellum 20:21, 28 декабря 2006 г. (UTC)
- и я также говорю, что все проблемы в NP могут быть решены за полиномиальное время (это может занять все пространство известной вселенной, но это все еще может быть решено за полиномиальное время). Я могу (теоретически) построить машину для решения всех задач класса NP за полиномиальное время, которая применяется к NP и делает излишним приведенное выше утверждение. Да, недетерминированные токарные станки являются неотъемлемой частью обсуждения NP, но это не означает, что массово-параллельные детерминированные алгоритмы следует игнорировать при обсуждении np-полноты. - АНОНИМНЫЙ COWARD0xC0DE 05:41, 23 декабря 2006 г. (UTC)
Все задачи классов NP и P являются подмножествами PSPACE, поэтому я оправдан. - АНОНИМНЫЙ COWARD0xC0DE 05:22, 30 декабря 2006 г. (UTC)
- Ваш аргумент является не только оригинальным исследованием, но и неприменим к проблеме. Предполагая в качестве аргумента, что вы действительно можете заставить каждую ячейку в экспоненциально воспроизводящейся культуре выполнять полезные проверочные вычисления, и вы могли бы поддерживать ресурсы, необходимые для роста этой культуры до полезных размеров проблемы, тогда вы могли бы решить проблему за полиномиальное время, но это не имеет значения, поскольку вопрос о том, P = NP, заключается не в том, могут ли произвольные вычислительные механизмы решать NP-задачи за полиномиальное время, а в том, могут ли это сделать детерминированные машины Тьюринга (используемые в определении P). Фактически, ваши идеи о ДНК-вычислениях / культуре клеток являются предполагаемыми физическими реализациями недетерминированной машины, которые, как часто говорят, «делают копии самих себя» для их понимания. Таким образом, неудивительно, что они могут решать задачи NP за полиномиальное время, поскольку NP определяется как задачи, решаемые недетерминированной машиной за полиномиальное время.
- Что касается вопроса о пространстве, детерминированные машины Тьюринга, используемые в определении P, никогда не занимают больше места, чем времени, и я перехожу к классам сложности P и NP, чтобы вернуть туда ваши избыточные дополнения. Деку 00:55, 1 января 2007 г. (UTC)
- Юзер: Меллум меня опередила, спасибо. Деку 00:57, 1 января 2007 г. (UTC)
- Я не уверен в том, что вы называете оригинальным исследованием, мое утверждение, что, поскольку NP является подмножеством PSPACE, я оправдан, или мое «доказательство». Насколько мне известно, машины Massively_parallel не являются недетерминированными, как и суперкомпьютеры. Я говорю только о космических проблемах. Позвольте мне прояснить это, я говорю о предложении «Следствием этого определения является то, что если бы у нас был алгоритм с полиномиальным временем для C , мы могли бы решить все проблемы в NP за полиномиальное время». Я прочитал это предложение как «Следствием этого определения является то, что, поскольку у нас есть алгоритм с полиномиальным временем для C , мы можем решить все проблемы в NP за полиномиальное время». Действительно, Меллум указал, что поливремени с таким же успехом может относиться к алгоритмам для недетерминированных машин Тьюринга. Вы говорите, что суперкомпьютеры не являются детерминированными машинами Тьюринга (я согласен с тем, что непараллельные машины никогда не используют больше места, чем время)? Думаю, я могу понять, почему вы продолжаете называть мое «доказательство» недетерминированным, потому что, когда я цитировал источник, он использовал ДНК-вычисления с недетерминированными аспектами, но в моем «доказательстве» были сформированы все возможные пути поиска, которые могли бы свести на нет любые недетерминированные эффекты. В то время я на самом деле не обращал никакого внимания на недетерминизм, только на примеры компромисса между пространством и временем, которые очень напоминали мое «доказательство». Я надеюсь, что это уточнение поможет. Просто наблюдение. Меллум заявил: «Ваше« доказательство »не использует недетерминированные машины Тьюринга», но Деку заявил, что «ваши идеи вычислений ДНК / клеточных культур являются предполагаемыми физическими реализациями недетерминированной машины», поэтому, как я кратко предположил в предыдущем предложении, я предполагаю, Вы имеете в виду мою цитату и другое моё «доказательство». - АНОНИМНЫЙ COWARD0xC0DE 12:18, 2 января 2007 г. (UTC)
- Вкратце: высокопараллельные машины с фиксированным числом параллельных процессоров могут быть смоделированы детерминированными машинами Тьюринга с замедлением не более чем с полиномиальным фактором, тогда как машины с количеством параллельных процессоров, которое увеличивается со временем, могут не моделироваться, и в частности, я не Я не знаю, как это сделать с двумя описанными вами моделями. Деку, 15:17, 2 января 2007 г. (UTC)
- Спасибо! Еще одно замечание, я думаю, не важно, что существует фиксированное количество процессоров, а важно только то, что максимальное количество используемых процессоров в любой момент времени по отношению к размеру проблемы является экспоненциальным, и, следовательно, нет полиномиального моделирования. на универсальной машине Тьюринга. Итак, хотя моя машина может быть детерминированной (не DTM, а только D) и массово параллельной, она не эквивалентна Тьюрингу и, следовательно, не актуальна. - АНОНИМНЫЙ COWARD0xC0DE 08:01, 3 января 2007 г. (UTC)
- Что ж, это эквивалент Тьюринга, просто прямое моделирование с помощью DTM требует экспоненциального замедления, так что DTM потребует экспоненциального времени, в то время как модель занимает политайм. Если P = NP, то он может смоделировать это за меньшее время. Но в этом вся суть. Вы правы в том, что если количество процедур полиномиально, то опять же симуляция возможна в разнонаправленном режиме. Деку 12:19, 3 января 2007 г. (UTC)
- Хорошо, у меня было заблуждение (принял возможность эмуляции за эффективную (многоразовую) эмуляцию). Итак, по сути, мои изменения в том, что если бы у нас был полиномиальный алгоритм времени (и пространства) для C , мы могли бы решить все проблемы в NP за полиномиальное время (и пространство). можно было бы сказать, как если бы у нас был алгоритм с полиномиальным временем (на UTM ) для C , мы могли бы решить все проблемы в NP за полиномиальное время. - АНОНИМНЫЙ COWARD0xC0DE 02:29, 10 января 2007 г. (UTC)
- Что ж, это эквивалент Тьюринга, просто прямое моделирование с помощью DTM требует экспоненциального замедления, так что DTM потребует экспоненциального времени, в то время как модель занимает политайм. Если P = NP, то он может смоделировать это за меньшее время. Но в этом вся суть. Вы правы в том, что если количество процедур полиномиально, то опять же симуляция возможна в разнонаправленном режиме. Деку 12:19, 3 января 2007 г. (UTC)
- Спасибо! Еще одно замечание, я думаю, не важно, что существует фиксированное количество процессоров, а важно только то, что максимальное количество используемых процессоров в любой момент времени по отношению к размеру проблемы является экспоненциальным, и, следовательно, нет полиномиального моделирования. на универсальной машине Тьюринга. Итак, хотя моя машина может быть детерминированной (не DTM, а только D) и массово параллельной, она не эквивалентна Тьюрингу и, следовательно, не актуальна. - АНОНИМНЫЙ COWARD0xC0DE 08:01, 3 января 2007 г. (UTC)
- Вкратце: высокопараллельные машины с фиксированным числом параллельных процессоров могут быть смоделированы детерминированными машинами Тьюринга с замедлением не более чем с полиномиальным фактором, тогда как машины с количеством параллельных процессоров, которое увеличивается со временем, могут не моделироваться, и в частности, я не Я не знаю, как это сделать с двумя описанными вами моделями. Деку, 15:17, 2 января 2007 г. (UTC)
Я беру это обратно, PSPACE означает только то, что проблема может быть решена с помощью алгоритмов полипространства, поэтому сам по себе этот факт не является оправданием. По какой-то причине я думал примерно так, что любой алгоритм для задачи PSPACE должен работать в полиномиальном пространстве. - АНОНИМНЫЙ COWARD0xC0DE 12:18, 2 января 2007 г. (UTC)
Что касается заголовка других сокращений
Я считаю, что раздел «В отношении других сокращений» следует переместить на следующую страницу: http://en.wikipedia.org/wiki/Polynomial-time_many-one_reduction . Я так и сделаю, если не будет возражений. Как славный плач ( разговор ) 08:14, 19 ноября 2007 (UTC)
- Я считаю, что это было бы неуместно. Это правильное место, чтобы обсудить это, потому что он включает в себя класс NP-complete и его определение, а не редукции в целом. Зачем вам его перемещать? Dcoetzee 07:56, 19 ноября 2007 г. (UTC)
- Этот раздел не подходит для данной статьи. Возможно, он плохо интегрирован. Как славный плач ( разговор ) 08:22, 19 ноября 2007 (UTC)
Вещи, которые необходимо добавить на эту страницу
1. Кратко обсудите, что кодирование задачи может повлиять на оценку сложности. В таких случаях следует использовать максимально сжатую кодировку. Это могло бы ответить на АНОНИМНЫЙ COWARD0xC0DE, вопрос, поскольку я считаю, что это то, о чем он говорит. страница 974 Введение в алгоритмы, второе издание, Cormen, Leiserson, rivest
2. Необходимо пояснить, почему «Чтобы доказать, что NP-проблема A на самом деле является NP-полной проблемой, достаточно показать, что уже известная NP-полная проблема сводится к A.»
3. Мы должны прояснить, почему наличие решения за полиномиальное время для 1 NP-полных задач приводит к коллапсу всего этого.
Никто не может: http://www.archive.org/details/CorrectionToTheoremOfCookwiki-version —Предыдущий неподписанный комментарий, добавленный 79.109.168.68 ( обсуждение ) 12:41, 7 марта 2011 г. (UTC)
4. Возможно, упомяните, что задачи NP - это задачи, которые могут быть решены на недетерминированной машине Тьюринга за полиномиальное время.
5. Поговорите о том, что NP-полные проблемы считаются менее решаемыми, чем проблемы P, и почему. —Предыдущий неподписанный комментарий, добавленный As the glorious weep ( talk • contribs ) 08:10, 19 ноября 2007 г. (UTC) As the glorious weep ( talk ) 08:15, 19 ноября 2007 (UTC)
Переименовать страницу в NP-Complete?
Согласно WP: MOS , «заголовки статей обычно состоят из существительных или их словосочетаний». Прилагательное NP-полнота - это форма существительного. Oren0 ( разговор ) 18:11, 28 ноября 2007 (UTC)
- Неа. «NP-complete» - это имя класса сложности, как и именная фраза. Dcoetzee 19:21, 28 ноября 2007 г. (UTC)
- Я бы также переименовал его в NP-полноту. «NP-Complete» обычно не используется как название класса сложности, но явно как прилагательное. Иллох ( разговор ) 13:01, 29 ноября 2007 (UTC)
- Он часто используется как имя класса в Complexity Zoo и во многих статьях. Это также установленная схема именования в Википедии (см. P-complete , Sharp P complete , EXPTIME-complete ). Это правда, что оно чаще используется в форме прилагательного, но это не означает, что существительное образует незаконное имя. Dcoetzee 23:05, 29 ноября 2007 г. (UTC)
- Даже если это слово можно использовать как существительное, в статье оно используется не так. Заголовок необходимо переписать, если мы имеем в виду NP-complete для ссылки на класс. Прочтите отрывок P-complete : «В теории сложности класс сложности P-complete ...» Обратите внимание, что P-complete используется как существительное. Сравните это с заголовком на этой странице: «В теории сложности NP-полные проблемы - это ...» Здесь NP-complete используется как прилагательное. Если на самом деле статья должна быть о классе, отрывок должен быть похож на IMO P-complete. Орен0 20:12, 3 декабря 2007 г. (UTC)
- Согласовано. Фиксированный. Dcoetzee 21:12, 3 декабря 2007 г. (UTC)
Введение для непрофессионалов
Я добавил общее введение для непрофессионалов. Я понимаю, что NP-complete не может быть точно описан в терминах непрофессионала, однако здесь необходимо сделать какое-то введение без жаргона. Точное введение для специалистов CS по-прежнему существует и сразу же следует за введением непрофессионала, поэтому ничего не было потеряно. - Клангин ( разговор ) 18:39, 6 июля 2008 г. (UTC)
- Хорошая попытка, но я все еще не могу понять вступление;) Серьезно, здесь требуется больше объяснений для среднего читателя. Я не имею ни малейшего понятия, о чем идет речь. Malick78 ( разговор ) 14:25, 14 февраля 2009 (UTC)
Я изменил определение на «быть в NP и быть NP-Hard» - по крайней мере, так я его усвоил и обнаружил, что об этом следует особо упомянуть в начале статьи. 114.36.56.75 ( разговорное ) 06:53, 25 июня 2010 (UTC)
НП-полный это КЛАСС ???
Я думаю, что это очень необычно, что авторы этой страницы настаивают на том, чтобы называть NP-complete КЛАССОМ СЛОЖНОСТИ. Грамматически «NP-complete» является ПРИЛАГАЮЩИМ. NP-полнота - свойство вычислительной задачи. Конечно, есть и соответствующий класс, но NP-полный - это не тот класс. Я думаю, что эта досадная особенность была исправлена ранее, но, кажется, кто-то хочет, чтобы это было по-другому. Прежде чем начать обсуждение этого вопроса, я предлагаю попытаться найти какие-либо доказательства в пользу идеи, что NP-complete является классом. Быстрый поиск в Google, похоже, не дает никаких доказательств этой идеи.
—Предыдущий комментарий без подписи, добавленный 203.143.165.107 ( обсуждение ) 01:02, 14 августа 2008 г. (UTC)
- NP-Complete - это и прилагательное, и класс. Есть много опубликованных источников, которые используют этот термин таким образом; попробуйте этот поиск Google . Его также иногда называют NPC. Dcoetzee 22:58, 14 августа 2008 г. (UTC)
Я не нашел "многих опубликованных источников" для этого утверждения. Эти статьи в Википедии, ошибочно утверждающие, что NP-Complete - это класс сложности (хотя это очень очевидно, как синтаксически, так и в обычном использовании компьютерными учеными, просто прилагательным), заставляют людей неправильно использовать это понятие. Я уверен, что так поступают и многие сбитые с толку молодые члены научного сообщества. Если вы посмотрите на авторитетный источник, такой как книга Пападимитриу «Вычислительная сложность», вы увидите, что в разделе 7.3 он определяет классы сложности как совокупность задач принятия решений, которые соответствуют заданным временным и пространственным ограничениям для данных моделей вычислений. В этом разделе упоминаются такие классы, как P, NP и PSPACE. В следующей главе, посвященной полноте, перечислены дополнительные классы, и никогда не говорится, что NP-complete является классом, и всегда и систематически NP-complete используется в качестве статьи. Это в точности то же самое, что и NP-hard, которое также является прилагательным, а не классом сложности. Конечно, для любого прилагательного (= свойства) можно определить класс объектов, удовлетворяющих этому, например NPC, но этот бесполезный и искусственный спор не об этом. Пожалуйста, спросите своего профессора о его / ее мнении о том, что NP-complete является классом сложности (а не просто прилагательным), и об этой статье в Википедии! (Я вижу, что dcoetzee - аспирант, который даже не занимается теорией сложности или чем-то отдаленно связанным. Тогда лучше не возитесь со статьями о сложности!)
Найдите АВТОРАТИВНЫЙ ИСТОЧНИК, например, учебник по теории вычислений, где NP-complete является классом. В противном случае я собираюсь заявить, что _mistaken_ мнение происходит из Википедии! —Предыдущий комментарий без знака добавлен 203.143.165.111 ( обсуждение ) 04:37, 4 ноября 2009 г. (UTC)
Как насчет главы 34 «Алгоритмов» Кормена, Лейзерсона, Ривеста и Стейна. Это де-факто стандартная книга алгоритмов. На странице 968 второго издания говорится: «Неформально проблема находится в классе NPC - и мы называем ее NP-полной - если она находится в NP, и она такая же« сложная », как и любая проблема. в НП ». Затем на странице 986 говорится: «Мы также определяем NPC как класс NP-полных языков».
Мне кажется, что эта книга определяет NP-complete как описание самых сложных языков (проблем) в NP. NPC - это класс NP-полных языков. - Предшествующий неподписанный комментарий, добавленный Etschreiber ( обсуждение • вклад ) 00:22, 12 февраля 2013 г. (UTC)
Внутреннее противоречие?
Во вступительном абзаце есть явное противоречие - или, по крайней мере, его формулировка сбивает с толку. Утверждение «Любое данное решение проблемы может быть быстро проверено» кажется противоречащим утверждению «Наиболее примечательной характеристикой NP-полных проблем является то, что для них не известно быстрое решение». 194.60.38.198 ( разговорное ) 14:40, 19 ноября 2008 (UTC)
- Они вовсе не противоречат друг другу. Данное решение может быть эффективно проверено, но нет известного эффективного способа найти решение в первую очередь. Я исправил , чтобы прояснить Dcoetzee 17:55, 19 ноября 2008 г. (UTC)
- Это выглядит немного яснее, хотя на самом деле при втором чтении я понял, что это было то, о чем он говорил. Спасибо. 194.60.38.198 ( разговорное ) 09:31, 20 ноября 2008 (UTC)
Открытие строк
Я должен признать, что довольно плохо знаком с вычислительной сложностью. Однако, основываясь на моем недавнем чтении, я не уверен, что первые строки правильно определяют NP-полную проблему: в теории вычислительной сложности класс сложности NP-complete (сокращенно NP-C или NPC, NP означает недетерминированное полиномиальное время) представляет собой класс задач, обладающих двумя свойствами: любое заданное решение проблемы может быть проверено быстро (за полиномиальное время); набор проблем с этим свойством называется NP. Если проблема может быть решена быстро (за полиномиальное время), то и каждая проблема в NP может быть решена.
Так где же здесь буква "N"? Несомненно, получение того, что оказывается правильным решением, может быть выполнено только с помощью недетерминированного автомата, и поэтому для завершения может потребоваться экспоненциальное время, верно? Физзакерли ( разговор ) 20:18, 16 апреля 2009 г. (UTC)
- Фактически, определение «можно проверить за полиномиальное время с помощью детерминированной машины Тьюринга» эквивалентно определению «можно решить за полиномиальное время с помощью недетерминированной машины Тьюринга». Мы избегаем упоминания о недетерминированных машинах Тьюринга в этой вводной статье, потому что они менее интуитивно понятны и требуют более подробного ознакомления. Кроме того, вы сбиваете с толку свою терминологию - недетерминированные автоматы определяют набор регулярных языков, который может быть определен за линейное время (все регулярные языки находятся в P). Кроме того, неизвестно, требуется ли для решения NP-полных задач экспоненциальное время (по сути, это и есть проблема P = NP, хотя вполне возможно, что кто-то может найти субэкспоненциальное, но суперполиномиальное решение для NP-полной проблемы, даже если П ≠ НП). Dcoetzee 08:57, 17 апреля 2009 г. (UTC)
- Было бы точнее сказать «результат« да »может быть проверен за полиномиальное время ...». Я думаю, что тот факт, что мы не знаем, можно ли проверить результат «нет» за полиномиальное время, вероятно, является ключом к окончательному доказательству. В то время как мой доктор философии Я занимаюсь человеческим фактором, а не теоретической информатикой, у меня есть некоторая подготовка, и я много лет возился с этой проблемой. Если бы кто-то смог доказать, что результат «нет» для чего-то вроде CLIQUE нельзя проверить за полиномиальное время, у вас было бы доказательство прямо здесь. К сожалению, трудно найти ссылки на такую работу для тех из нас, кто не в курсе (у кого-то есть указатель или два, которые можно предложить?) FWIW, я также думаю, что доказательство приведет к хорошему способу классификации различных подзадач / входов для различные NP-полные задачи (показывающие, как комбинаторика продвигает нас вверх от полиномиального к экспоненциальному и т. д. - отлично подходит для курсов первого или второго семестра по этому предмету). Мэтт Пламли 20:08, 26 сентября 2012 г. (UTC) - Предыдущий неподписанный комментарий добавлен Мэттплумли ( обсуждение • вклад )
Социальные последствия
Было ли что-нибудь написано о социальных последствиях NP = P? Я имею в виду, если NP Complete окажется легко разрешимой, что развалится? Безопасное шифрование? Смарт-карты? Личная конфиденциальность? Или ничего из этого? - BozMo talk 20:23, 16 апреля 2009 г. (UTC)
- Невозможно предсказать. Шифрование зависит от наличия некоторой практической односторонней функции лазейки - даже если все проблемы в NP решены эффективно, одна, вероятно, будет обнаружена на более высоком уровне сложности, используя преимущества новых эффективных примитивов для ее лазейки. Дкоутзи, 09:01, 17 апреля 2009 г. (UTC)
- Разве для шифрования вам не нужно иметь возможность проверять ключ в polytime? Короче говоря, разве любое шифрование, не основанное на NP, не потребует огромного времени для расшифровки, даже с ключом? 66.202.66.78 ( разговорное ) 07:49, 4 июня 2010 (UTC)
- Рассел Импальяццо написал широко цитируемую статью о некоторых последствиях различных результатов для неизвестных проблем, таких как P = NP и существование односторонних функций. Это стоит прочитать. Личный взгляд на сложность среднего случая . - Марк Доминус ( разговор ) 18:49, 4 июня 2010 г. (UTC)
Можно ли не учитывать, что NP-полные задачи также не решаются за полиномиальное время? это, несомненно, принесло бы мне пользу и более четко объяснило бы, что такое NP-Complete на самом деле. - SentinelAlpha ( разговор ) 16:08, 9 ноября 2010 г. (UTC)
- Но мы не знаем, разрешимы ли NP-полные задачи за полиномиальное время, в этом весь бизнес P vs. NP. Тот факт, что в настоящее время неизвестно полиномиальное решение NP-полных задач, упоминается в статье несколько раз. - Эмиль Дж. 16:25, 9 ноября 2010 г. (UTC)
Я создал алгоритм, который невозможно расшифровать. Демонстрация еще на испанском языке, но соответствие существует, и его нельзя обнаружить в его гильбертовом пространстве, потому что вероятность каждого символа ТОЧНО одинакова. Я запрограммировал пример на Python 3.0, если вам действительно интересно, свяжитесь со мной: [email protected] или прочтите о: http://www.archive.org/search.php?query=%22Juan%20Manuel%20Dato%22 It основан на создании соответствия данных и работе с ними для получения свойств сертификации, как в цифровых деньгах, но только с контейнерами экземпляров. Таким образом, мы не можем угадать, каковы значения экземпляров ..., почти, если мы не попробуем это один за другим.
Есть еще одно, чтобы продемонстрировать, что NP отличается от P, то есть с #P. Я заканчиваю свою теорию об этом, но я написал об этом книгу. Выводы между связью с энергией и энтропией поразительны. Но, конечно, я автор. Кому-нибудь интересно? У Американского общества есть проблемы с макетированием моих работ. Звучит слишком глупо! Вы знаете какой-нибудь журнал, в котором я могу показать свои работы? —Предыдущий неподписанный комментарий добавлен 79.109.168.68 ( обсуждение ) 12:35, 7 марта 2011 г. (UTC)
Студенты: руки прочь!
Пожалуйста, не редактируйте эту страницу, если у вас нет докторской степени и не менее 10 лет опыта работы в сфере CS. Товар не в хорошем состоянии. Предыдущее первое предложение, утверждающее, что NP-полный является классом сложности, - чистая чепуха. Конечно, вы можете определить класс сложности (класс задач решения), который совпадает с классом NP-полных задач, но нигде не определяется «NP-полный». Если вы считаете иначе, укажите АВТОРИТАТИВНЫЙ ИСТОЧНИК (Google или Википедия здесь не учитываются) - предшествующий неподписанный комментарий, добавленный 203.143.165.111 ( обсуждение ) 04:55, 4 ноября 2009 г. (UTC)
- NPC можно рассматривать как класс. Я не вижу в этом проблем. Любой набор проблем можно определить как класс сложности, и так уж случилось, что NPC - это класс. Если вам нужна ссылка, то вот статья: статья про зоопарк сложности про NPC . - Робин ( разговор ) 13:27, 4 ноября 2009 г. (UTC)
- Конечно, «исправление» этого НП содержит неверное определение, поэтому я не думаю, что мы должны слишком серьезно относиться к утверждению «не класс». В этом смысле французы семантически различаются, но большинство людей используют этот язык довольно свободно. - BozMo talk 20:03, 4 ноября 2009 г. (UTC)
- Если бы мы придерживались этих критериев применительно к вики, не было бы вики. Twin Bird ( разговор ) 23:11, 23 июля 2011 (UTC)
Ошибка формального определения?
"NP-полное - это подмножество NP, множества всех задач решения, решения которых могут быть проверены за полиномиальное время; NP может быть эквивалентно определено как набор задач решения, которые могут быть решены за полиномиальное время на недетерминированной машине Тьюринга. A проблема p в NP также находится в NPC тогда и только тогда, когда любая другая проблема в NP может быть преобразована в p за полиномиальное время. NP-Complete также может использоваться как прилагательное: проблемы в классе NP-complete известны как NP-complete проблемы."
Я почти уверен, что это неверно. Задачи NP не могут быть решены за полиномиальное время. В этом весь смысл, верно? Либо недетерминированная машина Тьюринга имеет особое свойство, кто-то пытался ее нарушить, либо кто-то где-то пропустил «нет» или «проверено». —Предыдущий комментарий без подписи, добавленный 148.85.245.244 ( обсуждение ) 13:53, 21 декабря 2009 г. (UTC)
- NP = Решаемая за полиномиальное время на недетерминированной TM. P = разрешимо за полиномиальное время на детерминированном TM. - Робин ( разговор ) 14:38, 21 декабря 2009 г. (UTC)
- Наверное, стоит (для людей, для которых недетерминированная ТМ - это гук) сказать NP = проверяемый за полиномиальное время? Или это технически неправильно? - BozMo разговор 7:34, 22 декабря 2009 (UTC)
- Это тоже нормально. В статье действительно говорится, что NP - это «набор всех задач, решения которых можно проверить за полиномиальное время». - Робин ( разговор ) 14:07, 22 декабря 2009 г. (UTC)
Пустая трата времени?
Опытный программист должен быть в состоянии распознать NP-полную проблему, чтобы он или она не тратить бессознательно время, пытаясь решить проблему, которая до сих пор ускользала от поколений компьютерных ученых.
Я не уверен, что согласен. Это как сказать: «Не тратьте время на последнюю теорему Ферма!» Что, если вы обнаружите новую NP-полную проблему, и окажется, что вы можете ее решить ... —Предыдущий комментарий без знака добавлен 159.171.152.2 ( обсуждение ) 11:00, 21 января 2010 г. (UTC)
- Это правда. Я изменил его, чтобы предложить программисту знать, что проблема является NP-полной, чтобы он / она знал, что это сложная проблема, и на практике есть способы ее решения, например алгоритмы аппроксимации. - Робин ( разговор ) 21:00, 2 апреля 2010 г. (UTC)
- Нет, это неправда. Вероятность того, что кто-либо решит сложные случаи NP-полной задачи (если N не очень мало) за разумное время, практически равна нулю. На неразрешимые проблемы тратятся колоссальные усилия, даже если не считать усилий тех, кто сознательно пытается добиться прорыва. Не каждый может быть Эндрю Уайлсом и даже таким, на который он потратил многие годы усилий. И, кстати, больше причин сомневаться в том, что NP = P, чем сомневаться в истинности и доказуемости последней теоремы Ферма . JRSpriggs ( разговор ) 00:46, 3 апреля 2010 (UTC)
- Есть ученые, которые считают, что P - это NP. Я не думаю, что Википедия должна выносить оценочные суждения о том, как люди используют свое время. Можем ли мы заменить слово «тратить» на «тратить»? С этим изменением будет сказано, что сознательно тратить время на проблемы с NPC лучше, чем делать это неосознанно. В отличие от текущей версии, в которой просто говорится, что тратить время на решение проблемы NPC - пустая трата времени. - Робин ( разговор ) 01:21, 3 апреля 2010 г. (UTC)
- Я не думаю, что вы должны делать оценочные суждения о том, что делать оценочные суждения - это плохо. (Таким образом вы противоречите себе.) Ничто в этой статье не заставляет кого-либо что-либо делать. Это просто предоставление им информации, которая может им помочь (или нет). Мое ценностное суждение состоит в том, что больше информации лучше, чем меньше информации. Поэтому я считаю, что версия, к которой я вернулся, лучше вашей. Суждение хорошее, если основано на фактах. JRSpriggs ( разговор ) 18:16, 3 апреля 2010 (UTC)
- Во-первых, я сказал, что Википедия не должна выносить оценочных суждений, а не я. Так что я себе не противоречу. Во-вторых, информация хорошая. Я полностью за программиста, зная, что он / она застрял с NP-полной проблемой. Я думаю, вы неправильно поняли, о чем я говорю. IP беспокоило то, что Википедия предлагает не работать над алгоритмами для NP-полных проблем, и я понимаю точку зрения IP. Советовать кому-то не работать над проблемой - это не факт, это ваше мнение (и мнение многих экспертов). Это не может быть заявлено в Википедии как факт, это можно констатировать как «многие эксперты верят ...» вместе с цитатой. - Робин ( разговор ) 18:52, 3 апреля 2010 г. (UTC)
- В версии, которую я вернул, говорилось: «... он или она знает, что эффективный алгоритм для этой проблемы ускользнул от поколений компьютерных ученых». что может быть истолковано как подразумевающее, что существует эффективный алгоритм (что, вероятно, неверно).
- Другая версия говорит , «... он или она не неосознанно тратить время , пытаясь решить проблему ...». Это просто стремится сделать человек осознает , что он мог бы тратить свое время, если он хочет работать над этой проблемой. В любом случае он по-прежнему может действовать. JRSpriggs ( разговор ) 19:13, 3 апреля 2010 (UTC)
- Как насчет того, чтобы заменить слово «тратить» словом «тратить», чтобы оно читалось как «... он или она не тратят время, неосознанно пытаясь решить проблему ...». Использование слова «отходы» предполагает, что попытки найти алгоритм для проблемы NPC - всегда пустая трата времени. - Робин ( разговор ) 21:34, 3 апреля 2010 г. (UTC)
- Сделанный. JRSpriggs ( разговор ) 02:32, 5 апреля 2010 (UTC)
NP = P?
Кто-нибудь видел это ? Я не видел никаких дискуссий по этому поводу, но, возможно, это может быть правдой. —Предыдущий неподписанный комментарий, добавленный Crazy FIZRUK ( обсуждение • вклад ) 10:04, 22 апреля 2010 г. (UTC)
- Статья короткая, написана на не очень хорошем английском языке и вряд ли будет правильной. - BozMo разговоры 20:31, 22 апреля 2010 (UTC)
Если-то характеристика полноты в свинце
Определение в заголовке состоит из двух частей (первая - NP). Вторая часть - характеристика полноты внутри NP. Я изменил его с «Если проблема может быть решена быстро (за полиномиальное время), то может и любая проблема в NP». на «Если бы оракул решал эту проблему, каждая проблема в NP была бы решена быстро (за полиномиальное время)». В моем резюме редактирования говорилось: «Конструкция ведущего: если-то игнорирует возможность того, что существуют проблемы NP, которые не являются ни P, ни NP-полными».
RobinK ( talk · contribs ) вернул меня, сказав: «Я не вижу проблемы; новый текст кажется более запутанным (и требует более продвинутой концепции оракула)».
Я изменил его только потому, что исходная версия может быть ложной . Предположим, что существует проблема A , которая не является ни P, ни NP-полной. « А можно решить за полиномиальное время». ложно. Отсюда вытекает импликация: «Если А можно решить за полиномиальное время, то можно и любую проблему в NP». должно быть правдой (см. материальный смысл, согласно которому). Таким образом, со старой версией отведения можно было бы сделать вывод, что A является NP-полным, но это не так.
Таким образом, я верну то, что Робин К. JRSpriggs ( разговор ) 08:42, 17 мая 2010 (UTC)
- В этом разделе статьи делается попытка охарактеризовать NP-полные проблемы. (начинается: " NP-Complete - это класс задач, обладающих двумя свойствами: ...) Обсуждаемое предложение гласит:
- Если проблема может быть решена быстро (за полиномиальное время), то и каждая проблема в NP может быть решена .
- «Проблема» здесь относится к гипотетической NP-полной проблеме. Таким образом, это означает, что если некоторая проблема A является NP-полной, и если A находится в P, то NP⊆P. Это правильно.
- Вы сказали: «Предположим ... A ... не является ни P, ни NP-полным», и пришли к противоречию. Но уже предполагалось, что A является NP-полным, поэтому неудивительно, что вы смогли сделать ложный вывод.
- Я думаю, что первоначальная формулировка была правильной, и я также считаю, что здесь нет необходимости вводить оракулы. - Марк Доминус ( разговор ) 12:57, 17 мая 2010 г. (UTC)
- Это должно быть грубое определение. Определение является эквивалентность между дефиниендумом (слово определяется, в данном случае «NP-полного») и его дефиниенса (выражение , которое дает его значение). Для того , чтобы работа, эквивалентность должна провести ли NP-полной истинно или ложно в задаче А . JRSpriggs ( разговор ) 17:22, 17 мая 2010 (UTC)
- Теперь я понимаю вашу точку зрения, спасибо. - Марк Доминус ( разговор ) 13:18, 18 мая 2010 г. (UTC)
- Теперь я понимаю вашу точку зрения, спасибо. Однако я все еще не думаю, что это лучший способ дать определение. Я имею в виду, что мы пытаемся достичь некоторого баланса между простотой и абсолютной правильностью, потому что это все еще неверно, как указано. Чтобы сделать это правильно, мы должны также указать, что вы можете использовать только 1 запрос и должны вывести ответ оракула (то есть редукцию Карпа ). - Робин ( разговор ) 20:58, 17 мая 2010 г. (UTC)
- To RobinK: Я вижу, что ваша точка зрения все еще неверна.
- Как мы можем сформулировать вторую часть определения одновременно правильным и еще более интуитивным, чем высказывание «Каждая проблема в NP сводится к C за полиномиальное время»?
- Как насчет «Любая проблема NP может быть преобразована в эту путем преобразования входных данных за полиномиальное время»? JRSpriggs ( разговор ) 01:56, 18 мая 2010 (UTC)
- Возможно, преобразование входных данных может дать интуитивное определение. Я не могу придумать лучшего, так что продолжайте. - Робин ( разговор ) 16:15, 18 мая 2010 г. (UTC)
- Сделанный. JRSpriggs ( разговор ) 05:17, 19 мая 2010 (UTC)
Определение
Второе свойство NP-полной задачи выражается в следующем: «Любую NP-задачу можно преобразовать в эту путем преобразования входных данных за полиномиальное время». Возможно, мне просто не хватает какого-то сложного математического термина, но я не понимаю, что означает «этот» - предшествующий беззнаковый комментарий, добавленный 129.170.26.240 ( обсуждение ) 13:11, 3 июня 2010 г. (UTC)
- «этот» означает «эта проблема (для которой мы определяем, что значит быть NP-полным)». JRSpriggs ( разговор ) 21:41, 3 июня 2010 (UTC)
Эвристика для задач планирования, может использоваться для других NP-полных задач.
Практическая, быстрая и эффективная эвристика для задач планирования времени может быть применима к другим NP-полным задачам.
Я являюсь автором бесплатного программного обеспечения под названием FET - бесплатное программное обеспечение с открытым исходным кодом - для составления расписания в школах, средних школах и университетах. Страница: http://lalescu.ro/liviu/fet/
Программа успешно применяется во многих учреждениях.
Поскольку FET - это быстрый эвристический метод для решения задачи расписания, которая является NP-полной проблемой, этот метод может быть применен к другим NP-полным задачам.
Примечание: под решением я подразумеваю эвристическое решение практических случаев, как это делает FET. Я не претендую на полиномиальное решение NP-полных задач.
Я пробовал алгоритм FET на других NP-полных задачах, но, к сожалению, он не дал мне удовлетворительных результатов. Может, я что-то упускаю.
Возможно, вам интересно рассказать об этом методе.
Описание алгоритма:
Алгоритм эвристический.
Вход: набор действий A_1 ... A_n и ограничения.
Вывод: набор времен TA_1 ... TA_n (временной интервал каждого действия. Комнаты здесь исключены для простоты). Алгоритм должен помещать каждое действие в определенный временной интервал, соблюдая ограничения. Каждый TA_i находится в диапазоне от 0 (T_1) до max_time_slots-1 (T_m).
Ограничения:
C1) Базовый: список пар действий, которые не могут быть одновременными (например, A_1 и A_2, потому что у них один и тот же учитель или одни и те же ученики);
C2) Множество других ограничений (исключенных здесь для простоты).
Алгоритм расписания (который я назвал «рекурсивным переключением»):
1) Отсортируйте занятия, сначала самые сложные. Не критичный шаг, но ускоряет алгоритм может быть в 10 и более раз.
2) Постарайтесь разместить каждое действие (A_i) в разрешенном временном интервале, следуя вышеуказанному порядку, по одному. Найдите доступный слот (T_j) для A_i, в который можно поместить это действие с соблюдением ограничений. Если доступно больше слотов, выберите случайный. Если ничего не доступно, выполните рекурсивную замену:
2 a) Для каждого временного интервала T_j подумайте, что произойдет, если вы поместите A_i в T_j. Будет список других действий, которые не согласуются с этим ходом (например, действие A_k находится в том же слоте T_j и имеет того же учителя или тех же учеников, что и A_i). Ведите список конфликтующих действий для каждого временного интервала T_j.
2 b) Выберите интервал (T_j) с наименьшим количеством конфликтующих действий. Скажем, список действий в этом слоте содержит 3 действия: A_p, A_q, A_r.
2 c) Поместите A_i в T_j и сделайте A_p, A_q, A_r нераспределенными.
2 d) Рекурсивно попробуйте разместить A_p, A_q, A_r (если уровень рекурсии не слишком велик, скажем 14, и если общее количество рекурсивных вызовов, подсчитанных с момента начала шага 2) на A_i началось, не слишком велико, скажем 2 * n), как на шаге 2).
2 e) Если успешно размещены A_p, A_q, A_r, вернитесь с успехом, в противном случае попробуйте другие временные интервалы (перейдите к шагу 2 b) и выберите следующий лучший временной интервал).
2 f) Если все (или разумное количество) временных интервалов были опробованы безуспешно, вернуться безуспешно.
2 g) Если мы находимся на уровне 0, и нам не удалось разместить A_i, разместите его, как в шагах 2 b) и 2 c), но без рекурсии. Теперь у нас есть еще 3 - 1 = 2 задания. Перейдите к шагу 2) (здесь используются некоторые способы избежать езды на велосипеде).
Ссылки:
FET: http://lalescu.ro/liviu/fet/
Лалескуливиу ( разговор ) 12:34, 7 февраля 2011 (UTC)
Лалескуливиу ( разговорное ) 15:19, 3 июня 2011 (UTC)
Лалескуливиу ( разговорное ) 15:20, 3 июня 2011 г. (UTC)
В отличие от теоремы Кука и ее определения
Если мы хотим понять, почему я могу убедиться, что теорема Кука неверна, сначала нам нужно будет прочитать его собственную транскрипцию: Теорема Кука в рецензируемой книге начинается с определения класса NP-Complete (стр. 37), как и набор Задачи NP, которые могут быть преобразованы в остальную часть NP с помощью кода, который по ресурсам времени не превышает более чем полиномиально (с учетом размера записи). Таким образом, если NP-Complete может быть решена в «поливремени», то каждый NP может получить реализацию (конфигурацию в машинах Тьюринга), стоимость которой также будет «поливремени»; для получения знаний NP = P.
При этом определение звучало очень интересно; но, конечно, целью Кука было продемонстрировать, что с этим свойством существует почти конфигурируемая в NP проблема. Демонстрацией существования этой NP-полной исходной проблемы является сама теорема Кука (стр. 39).
Рассуждения, сделанные г-ном Куком в этой теореме, состояли в том, чтобы утверждать, что проблема логической выполнимости может быть закодирована в разумную схему с помощью языка LSAT. Этот язык различает записи, которые принимают логическое значение в формуле, которую он представляет. То есть с помощью недетерминированной машины Тьюринга мы могли бы решить в «поливремени», удовлетворяет ли формула, описанная на языке, или нет.
После представления LSAT теперь нам нужно будет убедиться, что каждый язык L в NP может быть решен, если LSAT решался раньше за конкретное ограниченное время. Чтобы получить эту цель, мы будем использовать функцию fL (x), свойство которой состоит в том, чтобы распознавать каждый x в L тогда и только тогда, когда fL содержит задание, удовлетворяющее булевой формуле. Таким образом, мы поймем, что x является принятой записью для каждого NP и подключается к SAT с помощью f. Решая эту связь, мы будем решать за это ограниченное время каждую NP.
Работа этой функции будет заключаться в отображении каждой возможной возможности в его собственной машине Тьюринга, и, учитывая «поливремени», наша цель будет состоять в том, чтобы продемонстрировать только существование формулы, хорошо сформированной с той же силой, что и представленная проблема. И, на самом деле, процесс демонстрации продолжался следующим образом: если рассматривать машину, если она не детерминирована, граница будет зафиксирована полигоном, полученным по размеру записи (стр. 40), поэтому г-н Кук продолжил: « Это позволит нам полностью описать такое вычисление, используя только ограниченное число логических переменных и утверждение их истинности ». В этот самый момент каждый может сказать «да, в теории». Можем ли мы гарантировать, что каждая проблема NP, которую мы придумали (независимо от ее сложности), сможет быть преобразована в булеву формулу, представляющую ту же проблему? Когда Кук продолжил это утверждение, он упомянул «поли-количество» логических переменных, которые полностью не определены; с точки зрения математического формализма, эти переменные можно считать хорошо определенными, однако мы должны быть более строгими: существует ли соответствие между исходной задачей и формулой, хорошо сформированной для построения? Как сказать, это конструктивно? Более конкретно, построив формулу с каждой переменной, тогда мы только распознаем существование этих переменных как формулировки в порядке 0 (без какой-либо унификации), выполняя задачу L в решающей машине. То есть, если мы хотим построить хорошо сформированную формулу, прежде чем нам нужно будет знать решение проблемы.
По сути, это ошибка теоремы Кука: чтобы построить первое NP-полное, мы должны решить перед каждой возможной NP-проблемой. Очевидно, что это невозможно, потому что, решив логическую выполнимость, у нас не будет возможности найти код, позволяющий преобразовать проблему в любой другой NP.
С другой стороны, кроме теоремы Кука, подтверждающей существование этого кода, я не знаю никаких свидетельств о нем. Этот просвещенный код будет подходить к каждому небольшому достижению логической достоверности для решения каждой проблемы NP в целом; мы можем представить, что было бы, если бы этот код существовал, говоря о множестве преимуществ. Итак, если мы не понимаем, почему теорема ложна, мы почувствуем, что другого пути нет. Более того, не могли ли мы думать о решении проблемы Principia Mathematica как о ограниченной задаче во времени? Теорема Кука точно не определяет границу. Это только рефери, связанное с полиномом (без каких-либо выражений, ограничивающих использование). Что ж, давайте заменим слово полином на экспоненциальный или только ограниченный (он останавливается). Если у нас есть спецификация, описанная на основе аксиом Principia Mathematica, эта спецификация может быть продемонстрирована за ограниченное время любой машиной Тьюринга, чтобы получить омега-когерентность (почти, если мы используем разумный алгоритм унификации). Затем, если мы объединим доводы теоремы Кука с приложением к Principia Mathematica, мы всегда найдем формулу, удовлетворяющую логической логике порядка 0, удовлетворяющей формулировке Принципов. Итак, это противоречие с двумя наиболее известными результатами Гёделя: теоремами о полноте и неполноте.
Вот почему теорема Кука не может быть применена с теоретической точки зрения. —Предыдущий комментарий без подписи, добавленный 79.109.168.68 ( обсуждение ) 12:03, 7 марта 2011 г. (UTC)
Экспоненциальное время как заблуждение?
В разделе неправильных представлений экспоненциальное время выполнения перечисляется как заблуждение о NP-сложных задачах, утверждая, что «некоторые NP-полные задачи на самом деле имеют алгоритмы, работающие в суперполиномиальном, но субэкспоненциальном времени. Например, проблемы с независимым множеством и доминирующим множеством являются NP-полными, когда ограничен планарными графами, но может быть решен за субэкспоненциальное время ... "Мне совсем не ясно, что это правда. Учитывая, что все NP-задачи сводятся к любой данной NP-полной задаче за полиномиальное время, не означает ли это, что * все * NP-полные задачи разрешимы за субэкспоненциальное время? Это потребует обновлений на странице «Гипотеза экспоненциального времени», а также на странице «Временная сложность», на которой утверждается, что «Все самые известные алгоритмы для NP-полных задач, таких как 3SAT и т. Д., Требуют экспоненциального времени». Кроме того, цитируемый источник специально противопоставляет тот факт, что эти ограниченные задачи решаются за субэкспоненциальное время, с тем фактом, что, если мы предположим, что гипотеза экспоненциального времени верна, общая проблема не может быть решена за субэкспоненциальное время, потому что это NP -полный. Похоже, это убедительно свидетельствует о том, что ограниченные проблемы больше не являются NP-полными. Я не хочу вносить изменения сам из-за комментария «если у вас нет ученой степени, держите руки подальше», но может ли кто-нибудь, обладающий некоторым авторитетом в этой теме, просмотреть этот раздел статьи? - Emertonom ( разговор ) 05:58, 30 мая 2011 г. (UTC)
- Статья правильная. Несмотря на то, что существует полиномиальное сокращение от проблемы A к проблеме B, это не означает, что если бы мы нашли алгоритм субэкспоненциального времени для проблемы B, это сокращение привело бы к субэкспоненциальному алгоритму времени для проблемы A. Это потому что полиномиальное сокращение времени может увеличить размер экземпляров на полиномиальную величину. Например, он может сопоставить экземпляр размера n проблемы A с экземпляром размера n 3 для проблемы B. - Робин ( выступление ) 21:00, 30 мая 2011 г. (UTC)
«Все случаи NP-сложной проблемы сложны» неверно на гораздо более глубоком уровне. Каждый конкретный случай прост и требует постоянного времени. Можно сделать два различных утверждения. (a) некоторые подклассы исходной задачи все еще NP-трудны, а другие нет (например, KNAPSACK с ограниченными весами). (b) некоторые примеры требуют больше времени для решения, чем другие (например, примеры 3-SAT с ~ 1 решением). Однако бессмысленно говорить, что решение конкретного случая требует экспоненциального времени. Кроме того, это эмпирическое утверждение, а не теорема. (У меня есть соответствующая ученая степень, но я не "википедист", может, кто-нибудь другой должен ее изменить) 132.65.16.64 ( разговор ) 10:35, 17 октября 2012 г. (UTC)
Диаграмма Эйлера неверна.
Я удаляю диаграмму Эйлера по причинам, изложенным на странице обсуждения . Twin Bird ( разговор ) 23:10, 23 июля 2011 (UTC)
Все еще неверно .... - Предыдущий неподписанный комментарий добавлен 173.77.144.116 ( обсуждение ) 09:30, 19 февраля 2012 г. (UTC)
Кто этот парень и что здесь делает его диссертация?
Может ли кто-нибудь объяснить, кто такой Дорн и Фредерик, и почему его диссертация продвигается в статье вики? Я думаю, что кто-то должен разъяснить это утверждение: «Кандидатская диссертация Дорна [8] фокусируется на субэкспоненциальных временных алгоритмах для NP-сложных задач». Я думаю, людей не волнует, о чем идет речь, а, скорее, о том, каково изложение его тезиса и как он его доказал или аргументировал в отношении «Решение NP-полных проблем требует экспоненциального времени». - Предшествующий беззнаковый комментарий добавлен 210.4.96.73 ( обсуждение ) 00:58, 31 октября 2011 г. (UTC)
- Я не думаю, что тезис является надежным справочным материалом для использования, поэтому его следует удалить в любом случае. Millertime246 ( разговор ) 01:03, 31 октября 2011 (UTC)
- Чтобы мой друг Фредерик не потерял здесь репутацию, он заслуживает полного доверия и его тезис великолепен. Он придумал алгоритмы субэкспоненциального времени для NP-сложных задач на плоских графах, и эти результаты были опубликованы в рецензируемых журналах. Таким образом, ссылка на его работу в этой части статьи имеет определенный смысл. Однако тот, кто добавил эту неуместную фразу, не понял или захотел троллить. Иллох ( разговор ) 16:11, 2 ноября 2011 (UTC)
Квантовые компьютеры.
Позволят ли квантовые компьютеры решать на них NP-полные задачи за полиномиальное время? Я не верю, но я не могу найти никаких ссылок. - Предыдущий неподписанный комментарий добавлен 149.156.82.207 ( обсуждение ) 15:45, 24 января 2012 г. (UTC)
- Квантовые вычисления говорят: «Существует распространенное заблуждение, что квантовые компьютеры могут решать NP-полные задачи за полиномиальное время. Это не известно, чтобы быть правдой, и, как правило, считается ложным». и дает ссылку на Бернстайна, Итана; Вазирани, Умеш (1997). «Квантовая теория сложности» . SIAM Journal on Computing . 26 (5): 1411. DOI : 10.1137 / S0097539796300921 .. Подобные вопросы обычно следует задавать в Википедии: Справочная служба , а не в пространстве для обсуждения статей. - Марк Доминус ( разговор ) 19:03, 24 января 2012 г. (UTC)
Тривиальные задачи не могут быть NP-полными
Проблема называется «тривиальной» тогда и только тогда, когда это пустой набор или набор всех входных строк. Таким образом, существует ровно две таких проблемы, обе в P. Эти проблемы, очевидно, не являются NP-полными, потому что им не хватает необходимого принятого или отклоненного экземпляра проблемы, который должен быть в состоянии предоставить редукция отображения. Обратите внимание, что поли-временные редукции - это редукции отображения (редукции Карпа), а не редукции Тьюринга (редукции Кука).
Если P = NP, то каждая задача в NP также будет NP-полной, за исключением тривиальных проблем. Следовательно, мы знаем, что NP! = NP-полная. Правую часть этой диаграммы следует соответствующим образом обновить.
У меня нет под рукой своего экземпляра «Теории вычислительной сложности» Ду и Ко, но я считаю, что там есть упражнение, иллюстрирующее этот момент.
Торафобия ( разговор ) 05:38, 29 января 2012 (UTC)
- Concur. Пока схема не исправлена, ее следует удалить. aprock ( разговор ) 23:17, 19 марта 2012 (UTC)
Любая NP-задача, полиномиально сводимая к NP-полной?
Я чувствую заявление
"Проблема решения L является NP-полной, если она входит в набор NP-проблем, так что любое данное решение проблемы решения может быть проверено за полиномиальное время, а также в наборе NP-сложных проблем, так что любая NP-проблема может быть проверена за полиномиальное время. быть преобразованным в L преобразованием входных данных за полиномиальное время ".
неправильно. Утверждение означает, что «любую NP-задачу можно полиномиально преобразовать в NP-полную». Это правильно? Если это так, то P-проблемы также будут полиномиально сводимы к NP-полным задачам.
Пожалуйста, поправьте меня, если я ошибаюсь. - Абхинай Вишвакарма ( выступление ) 06:54, 30 января 2012 г. (UTC)
- Утверждение правильное (хотя мне не нравится его формулировка). Любая проблема из P поливремени сводится к любой NP-полной проблеме. Редукция довольно тривиальна для задач в P: редукция, по сути, состоит в том, чтобы решить проблему сразу, а затем, в конце, создать соответствующий экземпляр NP-полной проблемы.
- Торафобия ( разговор ) 14:49, 30 января 2012 (UTC)
Круговые определения
Первоначальные определения NP-сложных и NP-полных страниц определяют их предмет в терминах друг друга.
NP-трудная страница: проблема H является NP-сложной тогда и только тогда, когда существует NP-полная проблема L, которая полиномиально по Тьюрингу сводится к H
NP-полная страница: проблема решения L является NP-полной, если она входит в набор NP-задач, а также в набор NP-сложных задач.
Я не знаю достаточно по этому поводу, чтобы быть уверенным, как это исправить, но я думаю, что по крайней мере одно из определений можно расширить, чтобы не использовать другое.
172.4.233.15 ( разговорное ) 17:27, 7 апреля 2013 (UTC)
- NP-трудной статья довольно запутанная. Определение должно заключаться в том, что проблема является NP-сложной, если каждый NP-язык может быть сведен к ней, и, более того, для нее необходимо использовать редукции «многие единицы», а не сокращения Тьюринга ». - Эмиль Дж. 14:40, 8 апреля 2013 г. (UTC)
Я только что сделал такой же комментарий на странице NPH, прежде чем это заметил. Во введении здесь говорится: «Проблема решения L является NP-полной, если она входит в набор NP-проблем, а также в набор NP-сложных проблем». Это может быть правдой, но это довольно бесполезно как определение или объяснение, если NPH определяется только с точки зрения решения NPC. В свете того, что находится в основной части этой статьи, я неосведомленно предполагаю, что они должны сказать, что NPH включает в себя любую проблему, решение которой может быть использовано для решения всех проблем NP (за время полифонии для каждой из них), и что NPC - это подмножество проблем NPH, которые на самом деле сами находятся в NP. Если это верно, то я бы сказал здесь что-то вроде: «Проблема решения L является NP-полной, если она входит в набор проблем NP и может использоваться для решения любой другой проблемы NP только за полиномиальное дополнительное время. (Проблемы с последнее свойство называется NP-Hard, поэтому NPC - это просто пересечение NPH с самим NP) ", а на другой странице я бы сказал:" Проблема H является NP-сложной тогда и только тогда, когда каждая проблема NP является полиномиальным временем Тьюринга- сводится к H. " Конечно, из этого следует, что H2 гарантированно будет NPH, если в NPH есть некоторый H1, который можно свести к H2, и, в частности, если есть проблема NPC, которая настолько сводима (но я не уверен насчет «только если» в претензия теперь на странице NPH, если мы не знаем, что NPC непустой). 96.49.194.82 ( разговорное ) 02:01, 5 июля 2013 (UTC)
- Эта страница просто не написана для людей без опыта работы в этой теме. Не идеальная ситуация для нашей общей энциклопедии. Апокалипсис Клеопатры ( разговор ) 23:30, 23 апреля 2019 (UTC)
- Я согласен; однако сам предмет обсуждения чрезвычайно труден для понимания. На мой взгляд, человек, действительно разбирающийся в предмете, должен уметь объяснить его простыми словами, понятными человеку, не обладающему специальными знаниями. Это высокая планка. Я не знаю, как можно объяснить эту тему такими простыми словами; Думаю, это означает, что я не совсем понимаю тему.
- Сам термин «НП» сбивает с толку; это означает «недетерминированный многочлен», но он не относится ни к многочлену, ни к чему-то недетерминированному. Это относится к проблеме, которая может быть решена недетерминированной машиной Тьюринга за полиномиальное время. Как это следует распечатать человеку, не знакомому с предметом? Если трудно объяснить «NP», то насколько сложнее должно быть объяснить «NP-сложный» и «NP-полный»? MrDemeanour ( разговор ) 10:27, 24 апреля 2019 (UTC)
- Я не думаю, что это определение является точным круговым, потому что два его неопределенных термина (NP и NP-hard) ведут к статьям, соответствующие ссылки здесь не возвращаются. Но использовать подобные технические термины в главном предложении бесполезно, как из-за WP: TECHNICAL (мы должны сделать наши статьи читаемыми для максимально широкой аудитории), так и из-за того, что, когда мы определяем концепции, мы должны делать это с точки зрения более простых концепций. и ни NP, ни NP-hard не достаточно просты. Я бы предпочел начать что-то вроде:
- С точки зрения вычислительной сложности проблема является NP-полной, когда ее можно решить с помощью ограниченного класса алгоритмов перебора и ее можно использовать для моделирования любой другой задачи с помощью аналогичного алгоритма. Точнее, каждый вход проблемы должен быть связан с набором решений полиномиальной длины, достоверность которых может быть проверена за полиномиальное время, так что выход для любого входа будет «да», если набор решений не пуст и « нет ", если он пуст. Класс сложности задач такого вида называется NP . Задача называется NP-сложной, если все в NP может быть преобразовано в нее за полиномиальное время, и проблема является NP-полной, если она одновременно NP и NP-сложна. NP-полные задачи представляют собой самые сложные проблемы в NP. Если любая NP-полная задача имеет алгоритм с полиномиальным временем, то все задачи NP имеют.
- - Дэвид Эппштейн ( разговор ) 00:20, 24 апреля 2019 г. (UTC)
- Мне нравятся неформальные термины «проверить» (для «недетерминированных»), «решить» (для «детерминированных») и «быстро» (для «полиномиальных») во 2-м абзаце. Они часто используются во введении к статьям википедии, связанным с NP. Например, проблема P по сравнению с NP объясняется в одном предложении с использованием этих терминов. Поэтому я предлагаю начать нашу статью с объяснения (начиная с «Неформально, ...»), основанного на этих терминах. После этого могло последовать объяснение Дэвида Эппштейна с префиксом «Точнее, ...». Моя первая попытка была бы:
- Неформально, проблема называется NP-полным , если любое решение может быть быстро проверено , и все другие проблемы с этим свойством можно решить , по существу , по крайней мере так быстро , как A .
- Возможно, в этом стиле можно было бы объяснить также "NP" (проблемы с быстро проверяемыми решениями) и "NP-hard" (проблемы с наиболее медленным решением внутри NP). - Йохен Бургхардт ( разговор ) 14:15, 24 апреля 2019 г. (UTC)
- Технически неверно, что «любая другая проблема с этим свойством может быть решена по существу с такой же скоростью, как A », потому что сокращения, необходимые для доказательства NP-полноты, изменяют размер ввода и, следовательно, меняют соотношение между размером ввода и запуском. время, и потому что в NP могут существовать неполные NP-проблемы с тем же свойством «все остальное, по крайней мере, так же быстро». - Дэвид Эппштейн ( разговор ) 16:10, 24 апреля 2019 г. (UTC)
- Я переработал предложенный Дэвидом Эппштейном текст во вводный абзац. XOR'easter ( обсуждение ) 16:12, 24 апреля 2019 (UTC)
- Моя попытка однострочного неофициального заявления:
В теории сложности вычислений , что NP-полные задачи являются наиболее сложными в классе задач , которые , как полагают, будет трудно решить , даже если проверка правильности какого - либо одного предлагаемого решения легко.
Слишком неформально? XOR'easter ( обсуждение ) 16:17, 24 апреля 2019 (UTC)
- Технически неверно, что «любая другая проблема с этим свойством может быть решена по существу с такой же скоростью, как A », потому что сокращения, необходимые для доказательства NP-полноты, изменяют размер ввода и, следовательно, меняют соотношение между размером ввода и запуском. время, и потому что в NP могут существовать неполные NP-проблемы с тем же свойством «все остальное, по крайней мере, так же быстро». - Дэвид Эппштейн ( разговор ) 16:10, 24 апреля 2019 г. (UTC)
Заблуждение о том, что «если P = NP, все криптографические шифры могут быть взломаны»
Да, это заблуждение, но следующее утверждение из статьи не соответствует действительности:
Например, шифры с фиксированной длиной ключа, такие как Advanced Encryption Standard, могут быть взломаны за постоянное время (и, таким образом, уже находятся в P), хотя эта константа может превышать возраст вселенной.
Не существует решения с постоянным временем для AES (и они еще не в P), но это не объясняет и не устраняет фактическую причину, по которой криптографические шифры не обязательно будут взломаны. Если решение, найденное для NP-полной проблемы, составляет O (N ^ 32), то это решение все еще является полиномиальным и, следовательно, P = NP. Однако решение будет таким же сложным, как перебор O (2 ^ N) для 256-битного ключа (~ 2 ^ 256 = ~ 256 ^ 32). В том же случае 2048-битный ключ был бы значительно менее безопасным (~ 2 ^ 2048 против ~ 2048 ^ 32) - что эквивалентно "только" 352 битам. Это может быть расширено до решения с постоянным временем (возможно, уже опровергнуто, не уверен) с постоянным значением 1x10 ^ 78 операций. Однако в этом случае решения с постоянным значением увеличение длины ключа совершенно бесполезно! Сведение к 8-битному ключу, конечно, по-прежнему будет проблематичным с точки зрения атаки методом грубой силы, но увеличение до 2048-битного ключа будет не лучше, чем 256-битный ключ против атаки с постоянным временем. 74.254.239.180 ( разговорное ) 15:47, 24 марта 2014 (UTC)
- Решение методом грубой силы - это решение с постоянным временем для фиксированной длины ключа; в случае AES-256 решение требует не более 2 ^ 256 попыток. Другой момент, если я вас правильно понимаю, заключается в том, что алгоритм полиномиального времени может быть столь же безопасным, если степень полинома достаточно велика. Я согласен, что это должно быть в статье, но было бы лучше, если бы у нас был источник, который мы могли бы процитировать. Кроме того, насколько я понимаю, если бы решение O (N ^ 32) было найдено для одной NP-полной проблемы, хотя оно, конечно, доказало бы, что P = NP, это не означало бы, что все проблемы NP могут быть решены не более чем за О (N ^ 32). Лучшее, что вы могли бы сказать, это то, что любая другая проблема NP может быть решена не более чем за O (N ^ (32 + K)), где K неотрицательно и зависит от конкретной проблемы. Вот как я понимаю, что означает полиномиальная эквивалентность NP-сложных задач. - agr ( talk ) 18:23, 27 марта 2014 г. (UTC)
Решение без ссылки
// Y1+
// =/=N0
M1
N0 никогда не производит выходных данных. Алгоритм всегда дает результат «M1», если от запрошенного оракула ответ «Да», и никогда не дает результата, если ответ «N0», даже на другие возможные фразы того же запроса. Поразительно, насколько здесь легко упустить изобретательность наших программистов. Большая часть решения уже присутствовала в той степени, в какой пионеры и эксперты в этой области предполагали и утверждали, что это возможно. В частности, применим комментарий к Великой теореме Ферма, такие глубокие теории во многих случаях требуются для решения в значительной степени мыслимых неразрешимых проблем, особенно в тех случаях, когда большая часть решения и доказательства в словах уже были известны специалистам в данной области. .
Алгоритм отвечает «Да» с «M1», когда результат, полученный в результате правильно заданного вопроса, никогда не дает результата «Нет» (записывается как N0), а дает только результат «Да». Неправильно сформулированные вопросы - это вопросы, которые невозможно решить, потому что они приводят к выводу «N» или «Нет», при котором компьютер никогда не дает m неправильно заданный вопрос. Если задан правильно заданный вопрос, компьютер в конечном итоге всегда будет возвращать вывод «M». Но, учитывая сложность вопроса и известные переменные, время, необходимое для решения NP-полной задачи, полностью зависит от конкретной области применения и конструкции этого алгоритма. Чтобы проиллюстрировать функции, вот наглядный пример:
Правильно заданный вопрос: «ПДУ не нужны новые батарейки?»
АЛГОРИТМ говорит: проверьте функцию кнопки, если он изменяет канал на телевизоре или громкость телевизора, компьютер, контролирующий пульт дистанционного управления, выдает результат «M». Вывод выводится: да - значит нет.
Неправильно заданный вопрос при поиске проблемы NP-Complete: «Есть ли в пульте дистанционного управления новые батарейки?»
Если проверка пульта дистанционного управления выявляет отказ кнопки переключения канала или громкости телевизора, ответ будет выводиться никогда, потому что это будет ответ «Нет» или «N». 50.20.186.81 ( разговорное ) 12:52, 2 июня 2014 (UTC)
Внешние ссылки изменены
Привет, друзья Википедии,
Я только что добавил архивные ссылки на одну внешнюю ссылку о NP-полноте . Пожалуйста, найдите время, чтобы просмотреть мою правку . При необходимости добавьте после ссылки, чтобы я не мог ее изменить. В качестве альтернативы вы можете добавить, чтобы я вообще не попадал на страницу. Я внес следующие изменения:{{cbignore}}
{{nobots|deny=InternetArchiveBot}}
- Добавлен архив http://web.archive.org/web/20090419082030/http://www.cs.lth.se:80/home/Rolf_Karlsson/bk/lect8.pdf на http: //www.cs.lth. se / home / Rolf_Karlsson / bk / lect8.pdf
Когда вы закончите просмотр моих изменений, установите для отмеченного ниже параметра значение true или не сообщите другим (документация по адресу ).{{Sourcecheck}}
По состоянию на февраль 2018 г. разделы страницы обсуждения «Изменены внешние ссылки» больше не создаются и не отслеживаются InternetArchiveBot . В отношении этих уведомлений на странице обсуждения не требуется никаких специальных действий, кроме регулярной проверки с использованием приведенных ниже инструкций инструмента архивации. Редакторы имеют разрешение удалить эти разделы «Внешние ссылки изменены» на странице обсуждения, если они хотят убрать беспорядок на страницах обсуждения, но перед массовым систематическим удалением просматривают RfC . Это сообщение динамически обновляется с помощью шаблона (последнее обновление: 15 июля 2018 г.) .{{sourcecheck}}
- Если вы обнаружили URL-адреса, которые бот ошибочно считал мертвыми, вы можете сообщить о них с помощью этого инструмента .
- Если вы обнаружили ошибку в каких-либо архивах или самих URL-адресах, вы можете исправить их с помощью этого инструмента .
Ура. - Cyberbot II Поговорите с моим владельцем : Онлайн 20:16, 9 марта 2016 г. (UTC)
Проблемы со схемой
«Справа - диаграмма ... на этой диаграмме стрелка от одной проблемы к другой указывает направление уменьшения». На схеме нет стрелок. Это попытка юмора Монти Пифона? Скрытый тест на IQ для студентов бакалавриата по информатике? Честно говоря, статья достаточно непрозрачная и без такой ерунды. Росс Фрейзер ( разговор ) 06:25, 23 марта 2016 (UTC)
- Несомненно, это имело больше смысла с исходным изображением, File: Relative NPC chart.PNG , которое выглядит почти так же, но со стрелками, а не линиями, соединяющими овалы. Оно было загружено в 2003 году, заменено другим изображением с тем же именем и не таким грубым внешним видом в 2004 году, заменено нынешним изображением в 2011 году (хотя это изображение было загружено в 2008 году и, похоже, не имеет иной цели, кроме такая замена) и был удален в начале 2012 года как не содержащий информации об авторских правах. В любом случае, будьте WP: BOLD и отредактируйте эту часть текста, чтобы она снова имела смысл. - Дэвид Эппштейн ( разговор ) 07:12, 23 марта 2016 г. (UTC)
Избыточность в определении
Я отменил редактирование определения в lede, по существу удалив пункт 2, который, AFAIK, является избыточным; возможность проверить решение за полиномиальное время действительно описывает вкус NP, но AFAIK * любая * проблема, решаемая за полиномиальное время на NTM, имеет решение грубой силы экспоненциального времени на DTM. Есть ли какой-то аспект этого, который мне не хватает? Снефтел ( разговор ) 10:30, 22 февраля 2021 (UTC)
- И наоборот, любая задача, которая имеет детерминированный алгоритм поиска с экспоненциальным временем в виде «цикла по всем возможным решениям полиномиального размера и запускает полиномиальный тест на каждом из них», может быть решена с помощью полиномиального недетерминированного TM. Мой опыт показывает, что новички с гораздо большей вероятностью поймут определение «это в NP, если у него есть поиск грубой силы», чем определение NTM, и что это определение с меньшей вероятностью приведет к распространенному заблуждению о том, что NP-полные проблемы не имеют алгоритмическое решение. - Дэвид Эппштейн ( разговор ) 17:06, 22 февраля 2021 г. (UTC)
- Пункт (1) эквивалентен пункту (2), но пункт (3), являющийся дополнительным требованием, является источником путаницы. Более того, «в больших классах временной сложности» не выражает никаких ограничений. А как насчет следующей альтернативной формулировки?
- В теории сложности вычислений задача является NP-полной, когда:
- детерминированная машина Тьюринга может решить , например , с помощью алгоритма поиска перебора, и может проверить свои решения за полиномиальное время (эквивалентно: недетерминированный машин Тьюринга может решить за полиномиальное время) , и
- его можно использовать для моделирования любой другой задачи с аналогичной разрешимостью.
- В теории сложности вычислений задача является NP-полной, когда:
- Я за опускание серого текста (так как мы лидируем); включение некоторых из них в сноску могло бы быть другой возможностью. - Йохен Бургхардт ( разговор ) 18:34, 22 февраля 2021 г. (UTC)
- Ваше предложение (с серым текстом или без него) мне нравится. Я думаю, по крайней мере, первый пример необходим, чтобы уточнить, что «за полиномиальное время» изменяет только проверку, а не решение. - Дэвид Эппштейн ( разговор ) 18:49, 22 февраля 2021 г. (UTC)
- Пункт (1) эквивалентен пункту (2), но пункт (3), являющийся дополнительным требованием, является источником путаницы. Более того, «в больших классах временной сложности» не выражает никаких ограничений. А как насчет следующей альтернативной формулировки?
Хотя это не моя область знаний, я изначально преобразовал предыдущее определение в список, чтобы убедиться, что связь между NP-C и терминологией машины Тьюринга явно указана, не предполагая, что обычные читатели будут знать, что один из первых двух пунктов логически ведет к другому и поэтому считает его избыточным. В конце концов, элементы списка не должны и, я бы сказал, не обязательно должны пониматься как логически независимые, а не дополняющие или взаимно включающие (мы также можем явно подчеркнуть это). Для лингвистического определения важнее всего эффективно вписать его предмет в концептуальные рамки, к которым оно принадлежит, выгодно соотнося его с наиболее релевантными конструкциями. В данном случае такими релевантными конструкциями являются DTM, NTM, полиномиальное время и экспоненциальное время (с некоторым акцентом на то, что это не единственный класс сложности высокого уровня). Для краткости, конечно, NP-полные проблемы могут быть определены без определения каждого из этих отношений, но я не думаю, что такой экономический подход был бы наиболее желательным с точки зрения образования. Асем Хидхр ( разговорное ) 22:48, 22 февраля 2021 (UTC)
- Готово . Чтобы учесть аргументы Ассема Хидхра , я также включил последнее серое подвесное предложение в качестве сноски, так что все соответствующие конструкции упомянуты (я думаю, экспоненциальное время не имеет прямого отношения; оно может вообще оказаться неуместным, если P = NP найдено). Я думаю, что соотношение пунктов должно быть понятно читателю; и если мы можем избежать такой структуры, как (1⇔2) ∧3, мы должны избегать ее. - Йохен Бургхардт ( разговор ) 17:07, 24 февраля 2021 г. (UTC)
- Открыто повторно в связи с повторяющейся путаницей и неиспользованием сноски: [3] [4] [5] . @ Йохен Бургхардт , @ Дэвид Эппштейн , @ Sneftel : вы все еще думаете, что остаточная избыточность в логической структуре (1⇔2) 3 перевешивает ее возрастающую ясность? Асем Хидхр ( разговор ) 14:55, 9 марта 2021 (UTC)
- Я делаю. Общий смысл списка элементов состоит в том, что элементы схожи в организационном отношении, что вы либо описываете одну вещь тремя способами, либо три вещи в одну сторону каждая. У меня нет проблем с указанием обоих избыточных критериев - на самом деле это то, что делала моя первоначальная редакция - но перечисление трех критериев и доверие читателям разобраться, что на самом деле есть только два критерия, кажутся мне излишне неясными. TBH, я не думаю, что использование списка (а не абзаца) обязательно является лучшим подходом; но если это так, то это не должно заслонять тот факт, что NP-полнота определяется двумя фундаментальными критериями, «прослаивающими» его жесткость. Снефтел ( разговор ) 16:34, 11 марта 2021 (UTC)
- Открыто повторно в связи с повторяющейся путаницей и неиспользованием сноски: [3] [4] [5] . @ Йохен Бургхардт , @ Дэвид Эппштейн , @ Sneftel : вы все еще думаете, что остаточная избыточность в логической структуре (1⇔2) 3 перевешивает ее возрастающую ясность? Асем Хидхр ( разговор ) 14:55, 9 марта 2021 (UTC)
Возражение против нынешней формулировки: неверно утверждать, что «детерминированная машина Тьюринга может решить ее, например, с помощью алгоритма поиска грубой силы, и может проверить свои решения за полиномиальное время» . Путаница здесь может заключаться в том, что значит «решить» NP-полную проблему. Детерминированная машина Тьюринга может генерировать возможные решения NP-полной проблемы, но любое такое возможное решение может быть принято как истинное решение только в том случае, если его можно проверить как истинное (а задача проверки может быть выполнена за полиномиальное время). И возможно, что решение не может быть найдено за полиномиальное время. С другой стороны, недетерминированная машина Тьюринга (при условии, что любой такой зверь существует) действительно может найти истинное решение NP-полной проблемы. Этот вопрос очень свеж в моей голове, потому что я написал программное обеспечение для NP-полной проблемы (похожей на проблему больниц и резидентов с парами), которая генерировала возможные решения, а затем должна была их проверять; Мне нужно было немного изменить исходную проблему, чтобы гарантировать, что я всегда смогу найти решение. - Рич Уэльс (не имеет отношения к Джимбо) 06:57, 20 марта 2021 г. (UTC)
- Возможно, вы неправильно прочитали нынешнюю формулировку. В формулировке нет ничего, что требовало бы, чтобы машина, которая его решает, была ограничена полиномиальным временем. Похоже, вы страдаете именно тем заблуждением, для устранения которого было предназначено это определение: неверно утверждать, что NP-полные проблемы не имеют алгоритмов, которые решают их точно и детерминированно. Чего у них нет, так это алгоритмов с полиномиальным временем . - Дэвид Эппштейн ( разговор ) 07:00, 20 марта 2021 г. (UTC)
- Мне до сих пор не понятно, что «детерминированная машина Тьюринга может решить » NP-полную задачу. Возможно, нам следует либо сказать «детерминированная машина Тьюринга может решить ее за неполиномиальное время», либо «недетерминированная машина Тьюринга может решить ее за полиномиальное время». - Рич Уэльс (не имеет отношения к Джимбо) 07:10, 20 марта 2021 года (UTC)
- Что смущает? Вы пишете алгоритм. Вы реализуете это как компьютерную программу. Это решает проблему. На это уходит много времени. Я не думаю, что большинство читателей имеют четкое представление о том, что такое недетерминированная ТМ; ты? И использование «неполиномиального» в этом контексте - очень плохая идея, потому что это не то, что означает NP, и мы не хотим поощрять идею, что это так. - Дэвид Эппштейн ( разговор ) 07:20, 20 марта 2021 г. (UTC)
- Richwales , я изначально использовал
Детерминированная машина Тьюринга может решить в больших временных сложности классов (например, EXPTIME , как в случае с поисковым перебором алгоритмами) , и он может проверить свои решения за полиномиальное время
в адрес почти точно ваше возражение. Асем Хидхр ( разговор ) 08:20, 20 марта 2021 (UTC)- Но введение других классов сложности, подобных этому, не дает хорошего определения. В любом случае, я не думаю, что нам вообще нужно говорить о машинах Тьюринга в упрощенном определении ведущей. Просто скажите, что это может быть решено с помощью алгоритма поиска грубой силы (и решения проверяются за полиномиальное время). Таким образом, мы сделаем его читаемым для тех, кто еще не знает, что такое машины Тьюринга. - Дэвид Эппштейн ( разговор ) 16:08, 20 марта 2021 г. (UTC)
- Мы должны постараться найти формулировку, которую нельзя было бы неправильно истолковать.
- Я предполагаю, что основная проблема заключается в том, что мы обращаемся к двум аудиториям: (1) читателям, которые никогда не слышали о классах сложности, детерминированных или недетерминированных машинах Тьюринга и т. Д., И (2) читателям, которые знают (некоторые из этих понятий). Для аудитории (1) текущая формулировка подходит (и сноску следует даже удалить, а «полиномиальное время» следует популяризировать как «быстро»); «решенный», вероятно, следует понимать как «решенный детерминированной программой», поскольку никакие другие модели вычислений не известны. Тем не менее, аудитория (2) будет ожидать объяснений относительно детерминированного и недетерминированного, понятия «имитировать» и т. Д.
- Как насчет того, чтобы дать объяснение дважды, для аудитории (1), а затем еще раз для (2), четко разделенных, например, «интуитивно, ...» и «точнее, ...»? В текущей версии уже присутствует «Точнее»; мы могли бы придать тексту после него ту же форму, что и текст перед ним, так что подробное соответствие становится очевидным (например, между «быстро» и «за полиномиальное время»). Это просто вопрос перемещения интуитивных понятий вверх (перед словом «точнее») и более формальных понятий вниз (после него). - Йохен Бургхардт ( разговор ) 17:25, 20 марта 2021 (UTC)
- Я бы согласился на вашу золотую середину, поскольку полное отсутствие упоминания этих понятий, даже если только в lede, я думаю, больше похоже на Простую Википедию, чем на enWP. Ассем Хидхр ( разговор ) 17:51, 20 марта 2021 (UTC)
- Мне кажется, что нынешний «алгоритм поиска грубой силой может решить эту проблему, и правильность решения может быть проверена за полиномиальное время» на самом деле (с небольшим пояснительным текстом о том, как ответ да / нет определяется из search) уже формализуемое и точное определение NP, такое, которое вашей второй аудитории уже хорошо осведомленных читателей было бы лучше усвоить, чем махинации с NTM, которые для большинства целей являются ненужным запутыванием. В частности, этим читателям важно понимать, что проблемы NP в некотором смысле легкие, а не трудные, определяя их в терминах знакомого способа их решения (алгоритм поиска грубой силы), а не того, что они не являются (настолько неполиномиальными, что вам придется использовать совершенно другой тип машины, чтобы даже их решить). - Дэвид Эппштейн ( разговор ) 18:14, 20 марта 2021 г. (UTC)
- Я бы согласился на вашу золотую середину, поскольку полное отсутствие упоминания этих понятий, даже если только в lede, я думаю, больше похоже на Простую Википедию, чем на enWP. Ассем Хидхр ( разговор ) 17:51, 20 марта 2021 (UTC)
- Но введение других классов сложности, подобных этому, не дает хорошего определения. В любом случае, я не думаю, что нам вообще нужно говорить о машинах Тьюринга в упрощенном определении ведущей. Просто скажите, что это может быть решено с помощью алгоритма поиска грубой силы (и решения проверяются за полиномиальное время). Таким образом, мы сделаем его читаемым для тех, кто еще не знает, что такое машины Тьюринга. - Дэвид Эппштейн ( разговор ) 16:08, 20 марта 2021 г. (UTC)
- Мне до сих пор не понятно, что «детерминированная машина Тьюринга может решить » NP-полную задачу. Возможно, нам следует либо сказать «детерминированная машина Тьюринга может решить ее за неполиномиальное время», либо «недетерминированная машина Тьюринга может решить ее за полиномиальное время». - Рич Уэльс (не имеет отношения к Джимбо) 07:10, 20 марта 2021 года (UTC)
@ Ассем Хидхр : Моего знания английского недостаточно, чтобы понять, что вы подразумеваете под « золотой серединой». В любом случае, я предлагаю включить как простое, так и формально точное объяснение; последнее выйдет за рамки простой Википедии.
@ Дэвид Эппштейн : Мне нравится ваш подход к объяснению NP-полноты, и я согласен с вами в отношении типичных проблем, наблюдаемых с аудиторией (2). Однако я считаю, что мы должны последовательно рассматривать, если не решать, эти проблемы в первую очередь. Тот, кто помнит, что «N» означает «недетерминированный», должен найти последнее слово в начале и найти ему объяснение. Это может быть сделано путем повторения объяснений («интуитивно… точнее,…»), пояснительных сносок или каким-либо другим способом. Другими словами, статья должна учитывать происходящую ненужную путаницу и помогать разобраться в ней. - Йохен Бургхардт ( разговор ) 16:37, 21 марта 2021 г. (UTC)
- @ Йохен Бургхардт :: Я попытался заменить сноску более длинным в тексте объяснением того, что означают части имени "NP-complete", что, я думаю, в любом случае стоит включить в ведущую роль. Я упомянул недетерминированные машины Тьюринга под буквой «N» и переместил «полиномиальное время» из маркера (заменив его на «быстрое») к объяснению. См. Специальный раздел: Diff / 1013452083 . - Дэвид Эппштейн ( разговор ) 18:07, 21 марта 2021 г. (UTC)
- Мне нравится - спасибо! Йохен Бургхардт ( разговорное ) 13:12, 22 марта 2021 (UTC)