P?=NP: возможный новый результат
Sep. 15th, 2003 01:55 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПоявился свежий препринт; один из авторов - известный учёный. В статье содержатся очень сильные утверждения по поводу несуществования формальных доказательств P!=NP (P?=NP - самая знаменитая нерешённая проблема в computer science; если вы ничего о ней не знаете, вряд ли всё остальное в этой записи будет понятно) Авторы утверждают в частности, что не существует формального доказательства P!=NP ни в одном полиномиальном (в смысле времени распознавания аксиом) омега-консистентном расширении PA (Peano Arithmetic). С практической точки зрения, это очень близко к "P!=NP недоказуемо", и если доказательство будет принято... многое в этой научной области изменится.
К сожалению, у меня совершенно нет никакой возможности в ближайшие несколько дней как следует прочитать этот препринт и попытаться проверить доказательства. Я пробежал глазами основные определения и теоремы - выглядит очень интересно и явно не любительские бредни. Если кто-то будет это читать в ближайшее время, расскажите о ваших впечатлениях, пожалуйста. Я постараюсь освободить время для чтения этого препринта ближе к концу рабочей недели или на выходных.
К сожалению, у меня совершенно нет никакой возможности в ближайшие несколько дней как следует прочитать этот препринт и попытаться проверить доказательства. Я пробежал глазами основные определения и теоремы - выглядит очень интересно и явно не любительские бредни. Если кто-то будет это читать в ближайшее время, расскажите о ваших впечатлениях, пожалуйста. Я постараюсь освободить время для чтения этого препринта ближе к концу рабочей недели или на выходных.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-09-14 04:47 pm (UTC)З.Ы. Правильно в комменте к другому посту заметили, все о быте, а Вы о прекрасном. :)
no subject
Date: 2003-09-14 05:52 pm (UTC)no subject
Date: 2003-09-15 12:21 am (UTC)Вот отчего бы после этих слов лже-кат не поставить?
no subject
Date: 2003-09-16 03:16 pm (UTC)Рассмотрим такую систему аксиом, совершенно дурацкую: аксиомы PA плюс P!=NP. Допустим (рассуждая от противного) что эта система аксиом омега-консистентна. Условию полиномиальной распознаваемости она очевидным образом удовлетворяет. Утверждение "P!=NP" в ней очень даже доказуемо. Применяем результат этих авторов (Theorem 38, page 37) и получаем противоречие. Следовательно, наше первоначальное допущение неверно и PA плюс P!=NP омега-инконсистентна. Отсюда немедленно следует, что P=NP фактически.
То есть если авторы в самом деле доказали то, что они говорят, что они доказали, то они доказали, что P=NP. Альтернативное предположение состоит в том, что я неправильно понял как их формулировку, так и Ваш пересказ.
no subject
Date: 2003-09-16 03:31 pm (UTC)no subject
Date: 2003-09-16 03:51 pm (UTC)Я посмотрел по MathSciNet: один из авторов (Okamoto) публикуется в журналах по Computer Science, но второй, Kashima, вроде, матлогик.
Интересный вопрос -- Вы, наверно, разбираетесь в этом -- каков характер отношений между теоретиками компьютерной науки и чистыми математиками в современной жизни? Похожи ли они на отношения между теорфизиками и математиками?
no subject
Date: 2003-09-16 04:10 pm (UTC)каков характер отношений между теоретиками компьютерной науки и чистыми математиками в современной жизни?
Трудно сказать; теоретики компьютерной науки сами очень сильно разбросаны по шкале "чистоты". У теорфизиков тоже есть, скажем, с одной стороны струнники, а с другой куда более приземлённые и близкие к физической реальности люди, но у компьютерщиков это ещё намного шире распылено. Поэтому, скажем, в теории графов очень нелегко провести границу между тем, что в ней делают математики, а что - компьютерщики; то же самое верно во многих областях комбинаторики и кое-где в матлогике.
Если же Вы имеете в виду личные отношения, типа степени презрения к разным областям из разных областей, внутреннюю политику итп., то я стараюсь как можно меньше на такие вещи внимание обращать ;) вообще мало есть вещей, которые ненавижу и не приемлю больше, чем внутри-академические разборки и политику.
no subject
Date: 2003-09-17 09:24 am (UTC)Упоминая теорфизиков, я имел в виду в первую очередь струнников (с которыми я сам математику почти не обсуждал, но наблюдаю вживе, как это делают другие математики). Там имеется известная ситуация: с одной стороны, научное взаимодействие математиков с физиками бывает исключительно продуктивно; с другой стороны, математику чрезвычайно трудно понимать, что физики говорят. Даже в тех случаях, когда физики и математики говорят об одних и тех же или очевидным образом тесно связанных вещах, они говорят о них на разных языках.
В общем виде, наверно, разница такая: даже самый неартикулированный и путающийся в своих мыслях математик отличает конкретные математические объекты от смутных идей или метафор, образованных от каких-то математических объектов. Употребление терминов по их прямому значению и их употребление в качестве смутных аллюзий -- резко разграничены. Высказывания о хорошо определенных математических понятиях отделены от разговоров о вещах, точного математического смысла не имеющих. Если человек такую границу не проводит и смешивает эти вещи -- он, видимо, не математик. Все это очевидно, впрочем.
your system is not PT extention of PA (probably)
Date: 2003-09-17 10:11 am (UTC)extension of PA ? According to the
definition of PT extension (page 9) you should be able to recognize by PTIME algorithm
the truth of axioms (depending on a parameter), rather than their syntactical form.
Lis
Re: your system is not PT extention of PA (probably)
Date: 2003-09-17 10:14 am (UTC)Re: your system is not PT extention of PA (probably)
Date: 2003-09-17 10:27 am (UTC)Re: your system is not PT extention of PA (probably)
Date: 2003-09-17 10:34 am (UTC)Re: your system is not PT extention of PA (probably)
Date: 2003-09-17 10:35 am (UTC)Re: your system is not PT extention of PA (probably)
Date: 2003-09-17 10:24 am (UTC)Lis
Of course "P=NP" is not a PT extension!
Date: 2003-10-10 03:45 pm (UTC)Like, introducing Power(x,y) function.
Conservative extensions don't increase power, only improve readability.