Обсуждение:Равенство классов P и NP
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
 | Статья «Равенство классов P и NP» входит в общий для всех языковых разделов Википедии расширенный список необходимых статей. Её развитие вплоть до статуса избранной является важным направлением работы русского раздела Википедии. |
 | Эта статья была предложена к переименованию 6 марта 2015 года. В результате обсуждения было решено оставить название Равенство классов P и NP без изменений. Для повторного выставления статьи на переименование нужны веские основания, иначе это может быть расценено как игра с правилами (см. пункт 8). |
Создаётся впечатление, что как только эту теорему докажут, сразу научатся быстро решать задачи. Странно. --Nxx 06:10, 10 марта 2006 (UTC)
- Именно так, если доказательство будет конструктивным (например, решат одну из NP-полных задач за полиномиальное время). Что странного? Abyr 17:23, 10 марта 2006 (UTC)
- Ага, только степени у полиномов окажутся запредельными, и эффект от нового решения появится только при достаточно больших объёмах задач. Ну это так, шутка. 00:50, 3 декабря 2006 (UTC)
- Блин, да тут парадокс какой-то логический рождается. Решение по определению нельзя быстро найти, так как уже 30 лет ищут (даже если найдут, то это не будет быстро). Или тут в формулировке этой задачи какие-то недочёты, или я уже совсем нелогичен. Кстати, задачи быстрее решаться не будут — будет известна только скорость решения, а не путь его нахождения. То есть это такой же эффективный показатель как среднее арифметическое по больнице. Callidus 03:56, 22 марта 2010 (UTC)
Я начал переводить соответствующую статью с английского. Постараюсь закончить когда-нибудь и призываю всех мне помочь. Например, нужно все это привести в человеческий вид.Rasim 12:38, 3 декабря 2006 (UTC)
Можно ли узнать параметры вандалов из БГУ (время, IP)? Устрою очную встречу с В.А.Мощенским и ректором. Шпаги|пистоли за свой счёт. Inry 10:55, 6 декабря 2007 (UTC)
Шаблон {{unsolved}} не руссифицирован, может от него совсем избавиться? --Илья 21:13, 19 сентября 2008 (UTC)
Неправильная картинка. Доказана вложенность класса P в класс NP, а на картинке они не имеют пересечений. Полагаю, надо убрать эту картинку и найти другую, или же просто убрать. А то может ввести в заблуждение.
-- dartkam 08 июня 2009
- Смотрите внимательнее. На картинке не имеют пересечений классы P и NP-Complete, причем оба они лежат внутри класса NP. Maxal 13:36, 27 июля 2009 (UTC)
Проблемой статей русской википедии, связанных со сложностными классами, является то, что люди путают, какие объекты эти классы включают. Это классы языков (или задач, говоря проще), но не алгоритмов. Поэтому для доказательства теоремы о соотношении классов P и NP надо либо решить одну из NP-полных задач за полиномиальное время, либо показать, что для таких задач полиномиального алгоритма в принципе не существует. А не искать алгоритм, который бы лежал в NP, но не в P.
85.192.14.1 09:31, 27 июля 2009 (UTC)
Вот мой вариант решения задачи NP=P: способ найти истинные значения конъюнктивной формы записи функции. Нужно будет посмотреть граф сведений, походу они там все попересводятся.
Если так, бабки переводите на счёт Российского футбольного союза, Фабио нужна зарплата :) 1428 Vladimir 11:55, 21 января 2015 (UTC)
Ссылка на статью Деолаликара
[править код]85.26.170.142 добавил в статью ссылку на доказательство Деолаликара. Как вы считаете, не слишком ли рано давать на него ссылку, учитывая, что доказательство пока еще не признано экспертами? В англовики пока воздерживаются от упоминания этого доказательства. -- X7q 06:55, 9 августа 2010 (UTC)
- Поддерживаю. Тоже обратил внимание на грамотное, на мой взгляд, решение по этому вопросу в обсуждении к англоязычной статье. Практически во всех положительно отзывающихся авторитетных источниках наряду с признанием «серьёзности» попытки упоминается о преждевременности каких-либо выводов. Пока что это упоминание, особенно одиноко стоящее в разделе «Попытки доказательства», не отражает реального положения с имеющимися на сей день попытками (коих достаточно) и положения этого доказательства по отношению к ним. К тому же на странице автора непосредственное упоминание публикации ныне скрыто, хотя раньше было. Если будет официальное объявление, то оно появится, вероятно, во второй половине августа (конференция в Хайдерабаде). Торопиться не стоит. 92.101.159.85 19:25, 10 августа 2010 (UTC)
- UPD: упоминание вернулось. 78.36.166.222 00:34, 12 августа 2010 (UTC)
п и нп
[править код]пэ меньше или равно нпэ. Точнее будет пэ меньше чем нпэ так как равенство в данном случае недопустимо по причине легкого опровержения- 7-2 больше чем 5. Отсюда- нпэ больше чем просто пэ хотя и равно ему. это как правое включает всебя частичку левого. иван.
Речь идёт полиномиальной сложности решения задач, тобиш сколько времени занимает решение на абстрактном компьютере, для неполимиальных задач возможно только поверить решение за полином. время. А равенство классов задач означает, что можно решать значительно быстрее.
Деревце как-то так весело выглядит Graph of NP-Complete Problems А задача с конъюнктивной формой записи логической функции, в самом корне наблюдается.
Барак прибавь институту Клэя денег пожалуйста, 10 миллионов на задачу, а то миллион баксов за задачу тысячелетия как-то несолидно, вот и Перельман и отказывается. 79.104.4.30 13:59, 3 февраля 2015 (UTC)
Подраздел "Похожие проблемы"
[править код]Имхо можно дополнить подраздел следующим:
- Проблема равенства классов R[англ.] и RE[англ.]. Классы не равны, проблема решена с доказательством существования нерешаемых проблем, например, проблемы разрешения и неразрешимости диофантовых уравнений в общем виде.