Обсуждение:Равенство классов P и NP

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Создаётся впечатление, что как только эту теорему докажут, сразу научатся быстро решать задачи. Странно. --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)[ответить]

1438 figure2

Вот мой вариант решения задачи 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)[ответить]

пэ меньше или равно нпэ. Точнее будет пэ меньше чем нпэ так как равенство в данном случае недопустимо по причине легкого опровержения- 7-2 больше чем 5. Отсюда- нпэ больше чем просто пэ хотя и равно ему. это как правое включает всебя частичку левого. иван.
Речь идёт полиномиальной сложности решения задач, тобиш сколько времени занимает решение на абстрактном компьютере, для неполимиальных задач возможно только поверить решение за полином. время. А равенство классов задач означает, что можно решать значительно быстрее. Деревце как-то так весело выглядит Graph of NP-Complete Problems А задача с конъюнктивной формой записи логической функции, в самом корне наблюдается.
Барак прибавь институту Клэя денег пожалуйста, 10 миллионов на задачу, а то миллион баксов за задачу тысячелетия как-то несолидно, вот и Перельман и отказывается. 79.104.4.30 13:59, 3 февраля 2015 (UTC)[ответить]

Подраздел "Похожие проблемы"

[править код]

Имхо можно дополнить подраздел следующим:

Makxsiq (обс.) 13:03, 15 ноября 2022 (UTC)[ответить]