Форум мехмата МГУ по высшей математике
| Пользователям: | Аксиома — это истина, на которую не хватило доказательств. |
Форумы > Математика > Математические новости > Тема |
Объявления | Последний пост | |
---|---|---|
Работодателям и кадровым агентствам: Размещение вакансий | 26.03.2008 03:07 | |
Запущен новый раздел «Задачки и головоломки» | 29.08.2019 00:42 | |
Книги по математике и экономике в добрые руки! | 10.08.2023 09:45 |
17.08.2010 01:27 Admin Дата регистрации: 24 года назад Посты: 1 984 | Математик из Индии претендует на решение задачи про сравнение классов сложности P и NP Новость о том, что сотрудник лаборатории Hewlett-Packard в Пало-Альто индиец Винэй Деолаликар (Vinay Deolalikar) написал статью, в которой сделал вывод, что классы сложности P и NP не равны, появилась в математических блогах еще в начале недели. Авторы и комментаторы этих блогов немедленно окрестили новость «сенсационной» и даже «революционной» и принялись бурно обсуждать детали доказательства и его значение для человечества. Однако официальные СМИ причем, в основном, западные, написали о Деолаликаре только сейчас. Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально. В общем-то, от задачи тысячелетия сложно ожидать, что она будет легкой для понимания. Как написано на сайте института Клэя «Приз за решение задач тысячелетия призван отметить некоторые из самых сложных проблем, с которыми математики пытаются справиться на рубеже двух тысячелетий». Раз уж сотни и даже тысячи математиков не смогли совладать с этими задачами, значит, они действительно неподъемные. Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза «классы сложности P и NP не равны». Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной. Такого рода задачи называют задачами класса сложности NP, и их очень сложно решить “в лоб” (то есть перебором всех возможных вариантов) за вменяемое время при помощи любых самых мощных суперкомпьютеров. Однако сам факт того, что задачу, правильный ответ на которую легко проверить (в нашем случае, просто сверившись с полученным от руководства списком), действительно нельзя решить в относительно короткие сроки при помощи, например, какого-нибудь хитрого алгоритма, строго не доказан. На языке математиков отсутствие такого доказательства записывается как знак вопроса в формуле «P = NP?». Как уже догадался читатель, задачи класса сложности P можно решить за адекватное время (ученые используют термин «полиномиальное время», который означает, что время решения задачи не превосходит полинома от размера данных). Еще один пример задачи класса сложности NP – это сборка мозаики вслепую. Вы легко можете определить, правильно ли уложены все кусочки, но вот получить, скажем, Мону Лизу из тысячи разноцветных кусочков, перебирая различные их сочетания, уже не так просто. Впервые вопросом о равенстве или неравенстве классов сложности P и NP одновременно задались сразу два математика – Стивен Кук (Stephen Cook) и Леонид Левин в 1971 году. С тех пор ученые безуспешно пытаются на него ответить. Доказательного утверждения, можно ли все-таки поставить знак равенства между P и NP ждут не только исследователи, интересующиеся исключительно фундаментальными аспектами математики (для них вопрос является по-настоящему животрепещущим). Эта задача тысячелетия чрезвычайно важна для специалистов, занимающихся теориями компьютерных вычислений и шифрования данных. Интерес последних, вообще-то говоря, должен разделять любой человек, который хоть раз платил за какие-то покупки в интернете своей кредитной картой. Когда вы посылаете реквизиты карты на адрес магазина, они отправляются туда в зашифрованном виде, причем чаще всего шифрование производится не по сложным схемам, о которых все мы знаем из книг о шпионах. В современных шифрах используется принцип больших чисел – передаваемая информация кодируется огромным количеством цифр (так называемый ключ), и на вскрытие этого кода злоумышленнику придется потратить столько времени, что эта задача потеряет всякий смысл. Но – если P все-таки окажется равно NP, это означает, что злоумышленник может найти способ вскрыть шифр достаточно быстро и похитить информацию о вашей карте. Или секретные документы КГБ. Или все что угодно. Чтобы успокоить тех, кто срочно побежал аннулировать свои карты, оговоримся, что на сегодняшний день большинство математиков полагают, что классы сложности P и NP не равны. Впрочем, эти предположения не подкреплены строгими доказательствами и основаны на опыте – до сих пор никому не удалось решить задачу класса сложности NP за полиномиальное время. Доказательство Деолаликара занимает 116 страниц (здесь его можно скачать в формате pdf). Пока статья индийского математика не опубликована в рецензируемом журнале (хотя, например, статьи Григория Перельмана, за которые институт Клэя присудил ему Премию тысячелетия, так никогда и не были опубликованы), и сам он подчеркивает, что это только предварительный вариант, а окончательная версия появится чуть позже. Так что формально математики, желающие публично оценить доказательство, должны дождаться выхода готового текста. Но неформально многие из них уже начали изучать статью Деолаликара и некоторые уже выступили с критикой используемого ученым подхода. А вот сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) поступил иначе – он пообещал отдать Деолаликару 200 тысяч долларов, если выяснится, что его доказательство верно. Свой поступок Ааронсон мотивировал так: «Если неравенство P и NP действительно будет доказано, то моя жизнь изменится настолько кардинально, что потеря 200 тысяч будет совершенно незначима». К этим словам трудно что-то прибавить. Lenta.ru |
23.08.2010 20:42 Дата регистрации: 14 лет назад Посты: 9 | Где статья? Page not found пишет мне при обращении на ссылку http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf |
24.08.2010 02:48 Admin Дата регистрации: 24 года назад Посты: 1 984 | Хм... Это world wide web, тут иногда удаляют документы, а странице переезжают с одного адреса на другой. Отслеживать такие измененя никто не сможет, да и не будет... Поехидничаю. А вы уверены, что вам стоит читать доказательство, если вы не догадались (поленились) отрезать у URL фрагмент по до имени автора и посмотреть что там на той страничке? :-) |
24.08.2010 14:04 Дата регистрации: 14 лет назад Посты: 9 | Я - простой человек! Извиняюсь за нескромность, но зачем тогда выкладывать ссылку? Будьте любезны, если у Вас есть копия статьи, то сделайте пожалуйста рабочую ссылку на файл. Ну, перешел по корневому адресу, увидел там список в алфавитном порядке работников из лаборатории Hewlett Packard, хотя странно почему даже биографии некого Деолаликара, доказавшего знаменитую проблему, там попросту нет или я чет недосмотрел. |
30.08.2010 02:35 Admin Дата регистрации: 24 года назад Посты: 1 984 | ... Попробую угадать, что "домашняя страница" автор находится здесь - Vinay Deolalikar - а вот угадывать какой из pdf файлов - соответствующая работа, причем последней редакции, я не буду. Пусть этим занимаются специалисты в теме и интересующиеся. Ну напишите автору претензцию, как он мол посмел удалить файл, на который сослалась Lenta.ru, новостную заметку которой мы перепечатали. |
Copyright © 2000−2023 MathForum.Ru & MMOnline.Ru Разработка, поддержка и дизайн — MMForce.Net |