?

Log in

No account? Create an account
p ?= np - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

p ?= np [янв. 4, 2017|07:02 pm]
Anatoly Vorobey
[Tags|, ]

Скотт Ааронсон, на замечательный блог которого я многажды давал ссылки, опубликовал обзорную статью о вопросе P?=NP - главной нерешенной проблеме информатики и одной из главных в математике (хотя не все математики с этим согласятся):

http://www.scottaaronson.com/papers/pnp.pdf

100 страниц текста, не считая библиографии - и лишь малая часть посвящена определениям и базисным вопросам - в основном речь идет о достижениях, перспективах, разных подходах... Текст написан для широкой аудитории "математиков, ученых и инженеров". Для заинтересованных гуманитариев есть другая статья, всего 50 страниц (полцены!) "Почему философов должна интересовать теория сложности". Впрочем, технарям она тоже вполне может показаться интересной:

http://www.scottaaronson.com/papers/philos.pdf

Распечатал обе статьи, потому что вторую хотел перечитать все равно. Если что-то пойму в первой, напишу рецензию отдельно :)
СсылкаОтветить

Comments:
[User Picture]From: anna_i
2017-01-04 05:20 pm
Моему мужу повезло писать диссертацию у Левина - одного из "родителей" этой задачи. Свою первую работу в этой области Левин сделал кажется лет в 17 и вообще не собирался её печатать - не считал достаточно серьёзной. Его научный руководитель, Колмагоров, заставил.
(Ответить) (Thread)
[User Picture]From: tandem_bike
2017-01-04 05:58 pm
даже я в курсе. ;-) однако хорошая у Крупского педигри. рассказала бы ты когда-ниб. почему он с таким потенциалом предпочел неакадемию. у меня это больной палец.
(Ответить) (Parent) (Thread) (Развернуть)
From: 011010011001011
2017-01-04 05:34 pm
Скотт пишет отличные статьи и обзоры, но как же нездорово, что для внешних наблюдателей theoretical computer science -- это потуги вокрут P vs. NP.
(Ответить) (Thread)
From: (Anonymous)
2017-01-04 07:12 pm
А расскажите для меня, как внешнего наблюдателя, вокруг чего там все на самом деле? (Ну, конечно, если речь всего лишь про complexity classes при использовании ораклов - тады ладно, тады дело всего лишь в том, что для меня P vs NP - немногие из практически реализуемых классов... А если еще что, кроме этого да еще сухого остатка типа проблемы неразрешимости - тогда пожалуйста расскажите!!)
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2017-01-04 07:26 pm
Ну, даже если говорить о классах, на практике вы наверняка используете и вероятностные вычисления и криптографию, а все это не совсем (а точнее совсем не) про P vs. NP, хотя все эти вопросы так, или иначе связаны с вопросом P vs. NP.
(Ответить) (Parent) (Thread) (Развернуть)
From: 011010011001011
2017-01-04 07:34 pm
Все самое интересное, на мой biased взгляд, происходит в алгоритмах, а не сложности. Например, одна из лучших теоретических работ последнего времени: https://arxiv.org/abs/1307.2205 . Если интересно, могу написать, почему я так думаю.

Еще много совершенно замечательного происходит в криптографии, и это даже сравнительно легко объяснить внешнему наблюдателю.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2017-01-04 07:32 pm
Ну это-то как раз логично, а вся остальная математика для внешнего наблюдателя - это остальные проблемы тысячелетия.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2017-01-05 07:41 am
Наверное, это не очень отличается от того, что для внешних наблюдателей математика - это теорема Ферма, физика - поиск бозона Хиггса итд.
(Ответить) (Parent) (Thread)
[User Picture]From: f137
2017-01-04 07:05 pm
Я хоть и не гуманитарий, но начну со второй статьи, пожалуй. После беглого взгляда, первая не произвела впечатление расчитанной на *широкую* аудиторию, пусть даже ученых и инженеров.
(Ответить) (Thread)
[User Picture]From: amarao_san
2017-01-05 10:05 am
Но там же одноколоночная вёрстка! Нельзя верить научным работам с одноколоночной вёрсткой.
(Ответить) (Thread)
[User Picture]From: buddha239
2017-01-05 07:08 pm
Ну, моим можно.:)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: f137
2017-01-05 08:30 pm
ДА! Я понял, почему мне не пошло с первой поытки!
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-01-05 02:41 pm

P=NP

Возможно будет интересна статья P=NP: https://arxiv.org/abs/1208.0954

Albert
(Ответить) (Thread)
From: (Anonymous)
2017-01-05 09:05 pm

Re: P=NP

35 revisions! Упорный товарисч.
Картинки напоминают Кодекс Серафини. Какой полёт мысли!
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-01-08 03:54 am

Re: P=NP

А что, она чем-то отличается скажем от остальных на https://www.win.tue.nl/~gwoegi/P-versus-NP.htm ?

Абстракт вообще напоминает знаменитый анекдот про телеграмму в Академию Наук:
"Дорогая АН зпт я доказал теорему Ферма тчк Главная идея: в уравнении а квадрат плюс бэ квадрат равно цэ квадрат переносим цэ квадрат в левую часть тчк Подробности письмом"
(Ответить) (Parent) (Thread) (Развернуть)
Re: P=NP - (Анонимно) Развернуть