Странно что он не из сколково.

Желтизна

шта?? проверки ещё не было.

Где Ъ-пояснение?

что, опять?

по ссылке учёный изнасиловал журналиста

Интуитивно понятно, что проверить намного проще, чем отыскать. Какой смысл было это доказывать?

А где ссылка на статью? Пока ссылочки на arXiv не будет, все это — хрень!

Пусть известно, что проверить можно за полином. А можно ли отыскать за полином?

дайте два

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

А, ты обратную задачу предлагаешь решить. Подозреваю, что нельзя.

По ссылке полное пони.

И вообще, пока статьи не будет указано, можно любой бред генерировать. Все равно никто не знает.

Как раз об этом и гипотеза, что можно.

Где-то здесь подвох: какой смысл решать задачу без проверки? Ну, нагенерируешь ты случайных чисел, а потом космические корабли будут падать на головы народа. Зато ведь как круто: посчитал быстрей, чем проверил!!!

Потрясающе, в списке доказательств, уже больше ста вариантов. Причем уверенно некоторые доказывают равенство, некоторые также уверенно доказывают неравенство. Два автора вообще утверждают, что равенство (неравенство) недоказуемо.

А вы говорите, интуиция.

почитай уже наконец

http://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP

там и пример есть

Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.

Гипотеза не об этом.

P - это те задачи, которые решаются за полиномиальное время и естественно проверяются. NP - те задачи, которые можно решить перебором, т.е. за экспоненциальное время, и проверить за полиномиальное. А вот можно ли решить эти переборные задачи из класса NP за полиномиальное время - вот в чем вопрос. Гениальная проблема: интуиция подсказывает, что нельзя, а формального доказательства нет.

А кто-то вообще предлагает доказательства равенства. Поскольку NP задач довольно много (несколько сотен известно, если не ошибся), и они друг к другу сводятся за полиномиальное время, то достаточно решить одну, чтобы решить их все без квантовых компьютеров и прочей алхимии.

решить их все без квантовых компьютеров

вы так говорите, как будто умеете их с квантовыми компьютерами решать

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

Я правильно понимаю, что если действительно докажут, что P = NP, то криптосистема RSA накроется медным тазом (в перспективе)?

да, только не докажут

Баян же

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Потрясающе, в списке доказательств уже больше ста вариантов.

Современный вариант игры «Весёлая ФермА», однако...

из той же вики выше: «Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.» Где именно накроется криптография? она и так периодически местами накрывается когда находят способ ускорения расшифровки...

например обычный паяльник резко сокращает время на перебор паролей, так и свой паяльник и для остального найдут

Я вот только не понял, где пруф того, что в процессе доказательства P?NP появится способ сведения любой NP задачи в P.

А мужик по ссылке сказал, что свел одну из NP задач в P, но ни слова о том, что это можно сделать для _любой_ NP задачи

то криптосистема RSA накроется медным тазом

Эллиптические кривые спешат на помощь. Серьезно.

RSA — всего лишь одна из многих систем открытого распределения ключей, и всего лишь одна из немногих систем выработки ЭЦП.

Кроме того, любая уважающая себя криптосистема поддерживает набор различных алгоритмов. Исключения, составляют системы, подверженные регулированию. Но это отдельный разговор.

Интересно, что для серьезных нужд RSA никогда и не пользовались. Буржуи пользовались DSA, мы пользовались ГОСТ. Давным-давно, что тот, что другой — эллиптический.

RSA широко используется в TLS, но гипотетическая атака на шифротекст RSA (которая еще и не факт что будет эффективной) при доказательстве P=NP, не приведет к тому что перехваченные TLS-потоки можно будет расшифровать.

Появится только уязвимость к man-in-the-middle атакам. На практике, это означает всего лишь ликвидацию всех существующих доверенных сертификатов ЦС. Но это — головная боль ЦС. На практике, эффективность MitM-атак вызывает очень и очень серьезные сомнения.

Странно что он не из сколково.

Не странно. Он из Челябинска.

свел одну из NP задач в P

Что-то не нашел этого по ссылке. Просто NP или NP-полную?

Здесь утверждается, что NP-полную.

мужик по ссылке сказал, что свел одну из NP задач в P, но ни слова о том, что это можно сделать для _любой_ NP задачи

Решение одной из NP-полных проблем за полиномиальное время означает решение всех.

Но новость ни о чем - «окончательные результаты исследования» (что бы под этим не подразумевалось) не опубликованы.

Решение одной из NP-полных проблем за полиномиальное время означает решение всех

Точно же. Только не ткнешь меня в ссылку на пруф? (Серьезно, что-то я торможу)

Только не ткнешь меня в ссылку на пруф?

ЕМНИП, это следует из определения NP-полной проблемы (они все сводятся друг к другу).

http://en.wikipedia.org/wiki/NP-complete

«A problem p in NP is also NP-complete if every other problem in NP can be transformed into p in polynomial time».

А, и правда, спасибо.

занимался поисками решения одной из сложнейших актуальных задач тысячелетия – равенства классов P и NP
одной из сложнейших актуальных задач тысячелетия

реально что ли?
самая наиактуальнейшая задача тысячелетия?

самая наиактуальнейшая задача тысячелетия?

Там же прямо написано - «одна из». И неявно - «одна из математических».

моя родная шарага. вангую фейл.

Чем дольше профессионалы не смогут найти опровержение предлагаемого Анатолием Васильевичем решения, тем более правильным будет признан результат.

Вот это круто!

«Задачи тысячилетия» — список нерешенных математических задач. Актуальные задачи тысячилетия — все кроме задачи Пуанкаре.