Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.1 (3) След. > >>    Поиск:
Автор	Тема: [из новостей] Математик из Индии претендует на решение задачи тысячелетия
daner Сообщений: 4593	[из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 14:57 Цитата: Новость о том, что сотрудник лаборатории Hewlett-Packard в Пало-Альто индиец Винэй Деолаликар (Vinay Deolalikar) написал статью, в которой сделал вывод, что классы сложности P и NP не равны, появилась в математических блогах еще в начале недели. Авторы и комментаторы этих блогов немедленно окрестили новость “сенсационной” и даже “революционной” и принялись бурно обсуждать детали доказательства и его значение для человечества. Однако официальные СМИ причем, в основном, западные, написали о Деолаликаре только сейчас. Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально. http://lenta.ru/articles/2010/08/12/np/ От себя добавлю: КРУТО!!! Впрочем нельзя сказать, что неожиданно и тем более, что это что-то кардинально изменит, так как на сегодня все работы все-равно выходят из предположения что они не равны. [Ответ][Цитата]
NO. Сообщений: 10700	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 16:25 Почему предположения, кто пробовал NP-алгоритмы должны ясно понимать что сравнивать P и NP трудно потому что разница очень велика, и вопрос об их равенстве вообще не возникает. Вот только студентами принято говорить что NP это плохо, они потом от него шарахаются, поэтому мало кто пробовал. Это проблема только у теоретиков. У практиков всегда больше и ограничений и фактов, они часто и теории понимают лучше чем "ученые". Которые якобы занимаются проблемой, а на самом деле просто всех озадачивают и потом даже не слышат ответы. [Ответ][Цитата]
shuklin Сообщений: 2053	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 16:27 Цитата: Автор: daner http://lenta.ru/articles/2010/08/12/np/ Доказательство Деолаликара занимает 116 страниц ... А вот сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) поступил иначе – он пообещал отдать Деолаликару 200 тысяч долларов, если выяснится, что его доказательство верно. Можно западозрить, что проверка такого доказательства на корректность является NP задачей )))) [Ответ][Цитата]
Манганиновый троль Сообщений: 52	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 17:12 Цитата: Автор: daner http://lenta.ru/articles/2010/08/12/np/ От себя добавлю: КРУТО!!! Впрочем нельзя сказать, что неожиданно и тем более, что это что-то кардинально изменит, так как на сегодня все работы все-равно выходят из предположения что они не равны. БРАВИССИМО! Очередной раз доказать то что в принципе доказать невозможно, не потому что это не верно, а потом что само понятие "доказать" лишь возможно в рамках определенной теории и только. Помню, что раз пять уже доказывали что NP!=P, и несколько десятков раз доказали что NP=P. Очередной "выкрик" гения (а расценивать это пока что можно только так, так как статья не прошла рецензию) нисколько не внушает. [Ответ][Цитата]
daner Сообщений: 4593	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 17:27 Цитата: Автор: Манганиновый троль БРАВИССИМО! Очередной раз доказать то что в принципе доказать невозможно, не потому что это не верно, а потом что само понятие "доказать" лишь возможно в рамках определенной теории и только. Ну и причем тут невозможно? Естественно, что любое доказательство есть доказательство в рамках конкретной теории, но от этого доказательство теоремы Пиффагора не становится менее строгим и полезным. Цитата: Помню, что раз пять уже доказывали что NP!=P, и несколько десятков раз доказали что NP=P. Очередной "выкрик" гения (а расценивать это пока что можно только так, так как статья не прошла рецензию) нисколько не внушает. пять раз доказали??? что-то сомневаюсь. Возможно ПЫТАЛИСЬ доказать или ДУМАЛИ что доказали? И да согласен, что статья свежачек и возможно очередная сломанная голова о стену NP=/=P. Посмотрим. Я к сожалению не достаточно математик, что бы судить подобные доказательства. Цитата: Автор: NO Почему предположения, кто пробовал NP-алгоритмы должны ясно понимать что сравнивать P и NP трудно потому что разница очень велика, и вопрос об их равенстве вообще не возникает. Во-первых, это сложности не алгоритмов, а задачь относительно алгитмов (разница существенная). Во-вторых, все это и так хорошо понимают (большинство, во всяком случае), вот только строгое доказательство, совсем даже не лишнее будет. Теоремой Ферма тоже все пользовались и практики (да и теоретики) с ней особенно не заморачивались, но все-же ее решение стало событием в Научном Мире (хотя реально, ничего из-за этого не изменилось). [Ответ][Цитата]
NO. Сообщений: 10700	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 18:36 Цитата: Автор: daner Во-первых, это сложности не алгоритмов, а задачь относительно алгитмов (разница существенная). Ну и какая характеристика задачи измеряется когда пишут O()-формулы? [Ответ][Цитата]
ИЦ Сообщений: 3747	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 22:17 В чем суть задачи? [Ответ][Цитата]
ИЦ Сообщений: 3747	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 22:30 Нашел: Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной. [Ответ][Цитата]
NO. Сообщений: 10700	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 22:43 ну вот тут вся разница в том сколько студентов, 400 или некое N [Ответ][Цитата]
Манганиновый троль Сообщений: 52	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 12 авг 10 23:09 Цитата: Автор: daner Ну и причем тут невозможно? Естественно, что любое доказательство есть доказательство в рамках конкретной теории, но от этого доказательство теоремы Пиффагора не становится менее строгим и полезным. Почему невозможно?, на самом деле как сложно ответь на этот вопрос... я подумаю и постараюсь ответить на него в следующий раз... Но не приводите аналогию с теоремой Пифагора это очень разные вещи: доказать что для любого прямоугольного треугольника сумма квадратов катетов равна квадрату гипотенузы одно, более близка аналогия: "доказать(математически) что вечного двигателя создать нельзя" .... можно только поставить за факт - что нельзя, это закон природы, а доказать... Цитата: пять раз доказали??? что-то сомневаюсь. Возможно ПЫТАЛИСЬ доказать или ДУМАЛИ что доказали? И да согласен, что статья свежачек и возможно очередная сломанная голова о стену NP=/=P. Посмотрим. Я к сожалению не достаточно математик, что бы судить подобные доказательства. Угу, пяток раз... доказывали (ДУМАЛИ что доказали) как минимум... И очередное сенсационно-накрученное журналистами доказательство уже не новизна. [Ответ][Цитата]
ИЦ Сообщений: 3747	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 13 авг 10 0:12 Цитата: Автор: Имеющий Цель Нашел: Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной. Нашел, но ничего не понял.Кто-нибудь обьясните подробнее.Какие в частности условия нужно выполнить и в чем проблема проверки. [Ответ][Цитата]
daner Сообщений: 4593	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 13 авг 10 0:14 Цитата: Автор: NO. Ну и какая характеристика задачи измеряется когда пишут O()-формулы? Когда пишут О(.) формулы -- говорят об алгоритмах. А когда говорят о классах сложности то говорят об иерархии сложности задач. т.е. например NP задачи, это задачи, для решения которых существует недетерминированный полиномиальный алгоритм. Существование полиномиального алгоритма для этих задачь - открытый вопрос (если конечно индус не сумел доказать теорему, а если сумел, то вопрос уже закрытый). [Ответ][Цитата]
daner Сообщений: 4593	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 13 авг 10 0:18 Цитата: Автор: Имеющий Цель Нашел, но ничего не понял.Кто-нибудь обьясните подробнее.Какие в частности условия нужно выполнить и в чем проблема проверки. Не засоряйте себе голову, а то еще память кончится. [Ответ][Цитата]
ИЦ Сообщений: 3747	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 13 авг 10 0:20 Цитата: Автор: daner Когда пишут О(.) формулы -- говорят об алгоритмах. А когда говорят о классах сложности то говорят об иерархии сложности задач. т.е. например NP задачи, это задачи, для решения которых существует недетерминированный полиномиальный алгоритм. Существование полиномиального алгоритма для этих задачь - открытый вопрос (если конечно индус не сумел доказать теорему, а если сумел, то вопрос уже закрытый). По логике оффнауки доказать можно любой бред.Зачем индус думал, если можно сказать любой бред, а потом сказать "следовательно доказано"?Все что нужно-придумать аксиоматику.Я прямо сейчас могу доказать эту теорему, а потом тут же опровергнуть.Даже не зная о чем там говорится.Я могу решить все задачи тысячелетия меньше чем за секунду. [Ответ][Цитата]
ИЦ Сообщений: 3747	На: [из новостей] Математик из Индии претендует на решение задачи тысячелетия Добавлено: 13 авг 10 0:32 - [Ответ][Цитата]
Стр.1 (3): [1]  2  3 След. > >>