Обсуждение:NP-полная задача

Сводимость по Карпу и прочие определения

Я там поправил оформление, но по сути всё равно какой-то рваный бред написан. Грамотные люди, поправьте там, чтоб не возникало вопросов типа что такое тут $\Sigma ^{*}$, что такое $x$, которое принадлежит языку L, что такое полиномиальное время, и как оно связано с алфавитами, языками и словами? Какое отношение вообще сводимость по Карпу и все эти алфавиты имеют к NP-полноте задач? И вообще — какого рода задачам можно оценивать такую полноту? Ведь «задачи» разные бывают, и даже не математические… Какими свойствами обладают эти NP-полные задачи, чем они характерны — но на понятном языке, без использования специальных математических абстракций! --Nashev 17:26, 19 февраля 2009 (UTC)

• Что делать: сложности на пути получения матобразования порождают трудноискоренимый Снобизм, мешающий общению с иными лицами, взаимопониманию самих матобразованных и даже самопониманию. Нередко это не замечается и лицами успешными и реально понимающими предмет. Понимающими, увы, лишь как Вещь в себе... 83.237.216.112 20:33, 15 февраля 2014 (UTC)

• • Дело не в "сложностях на пути", а в специфических личностных особенностях, дающих на этом пути преимущество, облегчающих его прохождение.81.177.127.114 10:16, 8 марта 2017 (UTC)MichaelMM

А что круче: полная или трудная?

Нельзя ли максимально, насколько только возможно, человекообразно, человеческим языком, тем его подмножеством, которое предназначено для людей - обозначить соотношение между NP-полными и NP-трудными задачами? (Пояснение: под "людьми" подразумеваются, конечно же, читатели с естественным высшим образованием, но не с исключительно математическим. Потому что даже с Физфаком - читать эту галиматью сложновато.)
81.177.127.114 10:22, 8 марта 2017 (UTC)MichaelMM

• Добавил неформальное пояснение. Если всё равно не понятно, поставьте шаблон {{проще}} внизу страницы. — Алексей Копылов 22:30, 8 марта 2017 (UTC)

Алексей, спасибо! Очень здорово, когда за статьёй следят. И тогда ещё немного конкретных вопросов. (Они, правда, друг с другом пересекаются, повторяются, а иногда явно и прямо "переспрашивают" то, что уже сказано в статье, но, надеюсь, Вы поймёте в целом, в чём состоит недопонимание, и ответите соответственно.)
1) Верно ли, что NP-полная задача - всегда также и NP-трудная?

• Верно — Алексей Копылов 17:21, 12 марта 2017 (UTC)

2) Верно ли, что NP-трудная задача не обязательно входит в класс NP? (Т.е. может доказанно входить, а может доказанно не входить.)

• Верно — Алексей Копылов 17:21, 12 марта 2017 (UTC)

класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи)

3) Что это за "задачи, которые «сложнее» их" (и, притом, к которым могут быть сведены NP-полные)? Это ещё какой-то класс?

• «сложнее» - это неформальное понятие. Специалисты говорят «A сводится к B», что интуитивно значит «сложность A не больше сложности B». Тогда NP-трудные задачи это те, сложность которых не меньше сложности NP-полных задач (т.е. NP-полные + те, которые сложнее их). В принципе можно рассмотреть класс задач, которые строго сложнее NP-полных (т.е. NP-трудные без NP-полных), но этого не делают. — Алексей Копылов 17:21, 12 марта 2017 (UTC)

NP-полная задача — ...задача ...из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время

4) Верно ли, что "любую другую задачу из этого класса" - в том числе и другую NP-полную? Т.е. можно ли сказать, что (с точностью до полиномиального по времени преобразования) существует всего одна-единственная NP-полная "метазадача" (причём на её роль можно выбрать любую NP-полную, дело вкуса), решение которой означает решение всех задач класса NP, в том числе всех остальных NP-полных?

• Верно — Алексей Копылов 17:21, 12 марта 2017 (UTC)

5) Аналогично: верно ли, что и NP-трудная задача "на самом деле" всего одна? Или это неверно, и NP-трудные - это не строгий класс, а как бы "те, с которыми ещё не разобрались до конца": уже установлено, что к ним сводится любая NP-полная, но ещё не доказано, что сами они входят либо не входят в класс NP?

• Неверно ни то, ни другое. NP-трудные задачи - строго определенный класс, он включает NP-полные задачи и многие другие. Чтобы доказать, что задача NP-полна, надо доказать, что она NP и доказать, что она NP-трудная. (Хотя часто, если говорят, что задача NP-трудная, то действительно имеют в виду, то что вы сказали, но формально говоря, NP-полные задачи, тоже NP-трудные). — Алексей Копылов 17:21, 12 марта 2017 (UTC)

6) Если да - то, возвращаясь к п.2, надо сказать иначе: верно ли, что NP-трудная задача - неизвестно, входит ли (т.е. покамест не доказано, что входит либо не входят) в класс NP? (Потому что если бы точно, доказанно входила - была бы NP-полной. Или одно другому не мешает?)

• одно другому не мешает — Алексей Копылов 17:21, 12 марта 2017 (UTC)

7) (Возвращаясь к п.3:) Или не так, и про NP-трудные точно известно (доказано), что они в NP входить не могут? Тогда ещё раз: что это за особый класс? Что в них такого, что "не пускает" их в NP? И почему про них нет специальной статьи, и вообще в целом, по Инету, не очень-то понятно, что это и зачем? (Тогда как строгое и продуктивное понятие про NP-полные ищется легко навскидку в сотне мест.)
213.24.127.217 10:49, 12 марта 2017 (UTC)MichaelMM

• Про некоторые доказано, что входят, про некоторые доказано, что не входят. Статья в английской википедии есть. Просто у нас никто не взялся ее написать. Там даже картика есть. Может ее надо вставить в нашу статью? — Алексей Копылов 17:21, 12 марта 2017 (UTC)

Спасибо! Картинка хорошая, по мне - конечно, в статье нужна, если правильная.
Только по ней один вопрос. Не собственно "по ней", но благодаря ней, благодаря наглядности. Что же, выходит, NP-трудная задача не обязательно входит в класс NP?! А... зачем тогда вообще они называются NP-трудные? Это же только в заблуждение вводит. Или в этом какой-то глубокий намёк? На что?
И, конечно, очень не хватает в русской "Вики" статьи с точным определением про NP-трудные. Хоть небольшой. А то, судя по обсуждению статьи "Класс NP", не только я затрудняюсь в этой классификации.
Кстати, а почему внизу статьи, в сводке "Классы сложности алгоритмов" - NP-hard нет вообще? Таки это "не совсем" строгий класс, а всё же скорее "то, что в другие не попало"?
213.24.126.123 07:54, 10 июля 2017 (UTC)MichaelMM

• Да, NP-трудная задача не обязательно входит в класс NP. Согласен, терминология нелогична. Надо не забыть ее поменять, когда я стану диктатором. :) Когда кто-то там напишет статью про NP-трудность, ее можно будет добавить в таблицу. Это строгий класс. — Алексей Копылов 05:56, 12 июля 2017 (UTC)
  • Спасибо! И иллюстрация очень на месте.

Да уж, пожалуйста, не забудьте. А то безобразие. А серьёзно - мой вопрос был, по сути, ради второй его части: нет ли в таком термине всё же некоторого, не увиденного мною, указания на что-то в аспекте классификации.

Сводная же таблица и сейчас более чем наполовину состоит из "красных" названий классов. И добавить такой же 'NP-hard' представляется совершенно нормальным, более того - необходимым, иначе закономерно возникает вопрос, что в нём такого особенного, кроме отсутствия статьи. Почему отсутствие статьи не мешает нахождению в таблице двух десятков других таких же, а ему мешает? Сразу мысль: значит, он не такой же. Или для этого нужны специальные особые Вики-полномочия?

И коль скоро перевод - в самом деле, штука трудоёмкая и ответственная, а Кто_то_там не торопится - не могли бы Вы хотя бы здесь, в "Обсуждении", дать ссылку хотя бы на правильное русское определение класса 'NP-hard'? Кому очень надо - найдёт. Только, для заметности, мне кажется, лучше бы отдельной темой.

81.177.127.7 07:12, 13 июля 2017 (UTC)MichaelMM

NP-полнота в сильном смысле

Задача называется NP-полной в сильном смысле, если у неё существует подзадача, которая...

Что такое в данном случае "подзадача"? Это же ключевой (потому что единственный) параметр определения, он должен быть очерчен очень чётко, а тут - вообще никак.

1. не является задачей с числовыми параметрами (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)

Почему "то есть"? Каким образом ограниченность каких-либо величин сверху мешает им быть числовыми параметрами?

2. принадлежит классу NP,
3. является NP-полной.

Согласно определению в этой же статье, "NP-полная задача — ...задача ...из класса NP". Получается, п.2 избыточен при наличии п.3. Если нет - почему?
213.24.126.123 08:15, 10 июля 2017 (UTC)MichaelMM

• Я этот раздел не понимаю. Поставил запрос источника. А вообще возможно лучше перевести вместо него статью en:Strong NP-completeness. — Алексей Копылов 06:13, 12 июля 2017 (UTC)