Моему мужу повезло писать диссертацию у Левина - одного из "родителей" этой задачи. Свою первую работу в этой области Левин сделал кажется лет в 17 и вообще не собирался её печатать - не считал достаточно серьёзной. Его научный руководитель, Колмагоров, заставил.

даже я в курсе. ;-) однако хорошая у Крупского педигри. рассказала бы ты когда-ниб. почему он с таким потенциалом предпочел неакадемию. у меня это больной палец.

Скотт пишет отличные статьи и обзоры, но как же нездорово, что для внешних наблюдателей theoretical computer science -- это потуги вокрут P vs. NP.

А расскажите для меня, как внешнего наблюдателя, вокруг чего там все на самом деле? (Ну, конечно, если речь всего лишь про complexity classes при использовании ораклов - тады ладно, тады дело всего лишь в том, что для меня P vs NP - немногие из практически реализуемых классов... А если еще что, кроме этого да еще сухого остатка типа проблемы неразрешимости - тогда пожалуйста расскажите!!)

Ну, даже если говорить о классах, на практике вы наверняка используете и вероятностные вычисления и криптографию, а все это не совсем (а точнее совсем не) про P vs. NP, хотя все эти вопросы так, или иначе связаны с вопросом P vs. NP.

Все самое интересное, на мой biased взгляд, происходит в алгоритмах, а не сложности. Например, одна из лучших теоретических работ последнего времени: https://arxiv.org/abs/1307.2205 . Если интересно, могу написать, почему я так думаю.

Еще много совершенно замечательного происходит в криптографии, и это даже сравнительно легко объяснить внешнему наблюдателю.

Ну это-то как раз логично, а вся остальная математика для внешнего наблюдателя - это остальные проблемы тысячелетия.

Наверное, это не очень отличается от того, что для внешних наблюдателей математика - это теорема Ферма, физика - поиск бозона Хиггса итд.

Я хоть и не гуманитарий, но начну со второй статьи, пожалуй. После беглого взгляда, первая не произвела впечатление расчитанной на *широкую* аудиторию, пусть даже ученых и инженеров.

Но там же одноколоночная вёрстка! Нельзя верить научным работам с одноколоночной вёрсткой.

Ну, моим можно.:)

ДА! Я понял, почему мне не пошло с первой поытки!

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

Albert

35 revisions! Упорный товарисч.
Картинки напоминают Кодекс Серафини. Какой полёт мысли!

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

Абстракт вообще напоминает знаменитый анекдот про телеграмму в Академию Наук:
"Дорогая АН зпт я доказал теорему Ферма тчк Главная идея: в уравнении а квадрат плюс бэ квадрат равно цэ квадрат переносим цэ квадрат в левую часть тчк Подробности письмом"