Челябинский математик решил одну из задач, тысячелетия, на миллион долларов...

Мужик конечно молодец, у меня другой вопрос: я один ни хуя не понял?

Чель...лябинск! Мужик! Анатолий Васильевич!

Мне кажется, вы путаете немного, класс N - это класс решаемых за полиномиальное время. А тут, даже если предположим, что архивирование происходит за O(n) времени(и при малой константе C), то все равно скорость архивирования будет не "пару секунд" а значительно больше упираясь в производительность железа на котором жмем. Да и вообще симметричное архивирование и сейчас происходит фактически за линейной время но с большой константой...

Пруф?

Я ни хуя не понял, но за науку +

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

Хэш не индивидуален, у разных фильмов может быть одинаковый хэш.

Ну это Вы батенька загнули ... По хэшу файлы восстанавливать ... Да и с архивами тоже.
Возьмите,например, обычную контрольную сумму файла, и попробуйте по ней восстановить сам файл.

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

Пиздеж чистой воды - это я как информатик могу сказать с уверенностью 99%. Если бы это было правдой, мир бы уже охерел от хаоса и взломов потому как большинство криптоалгоритмов построены на том, что P != NP.
Где ссылки на статьи?
Индус номер два, хотя даже хуже. Тот хотя бы обратное утверждал.

Физмат в запое до весны

BelBES

Зачем нам тратить неопределенно сколько времени для тупого перебора бесконечного числа вариантов результата, если мы знаем, что можно скачать фильм за конечно-определенный временной промежуток? Тут как бэ область применения мимо кассы ...

http://seasonvar.ru/serial-7791-Elementarno-2-season.html
2 сезон 2 серия.
Более популярно будет ))))))

И да, согласен, фейк..... это примерно то, что из MD5 восстановить информацию.....

Это сообщение отредактировал Michaelt - 14.12.2013 - 16:26

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

Насколько я верно понял , N=NP - это не числа в чистом виде , не переменные из больших таблиц и даже не философские нематериальные сущности - это тупо два объекта , причём любых. Причём второй объект HP получается путём хитрожопых манипуляций с первым объектом P за одну единицу времени.

Ну и собственно доказательство >

Имея точные инструкции житрожопых операций можно получить объект P за ту самую единицу времени. В случае с торрентом это не только контрольный кеш - но и порядок!! его получения.

В случае отсутствия точных инструкций хитрожопых операций с объектом P - придётся перебирать все варианты хитрожопых операций , при этом тратя на проверку одного варианта ту самую единицу времени. А количество вариантов бесконечно.

Ну и хуле тут доказывать равенство единицы времени и бесконечности.????
В былые времена таких алхимиков на кол сажали, а сейчас (бля) они ещё и славу себе зарабатывать умудряются.

дайте ссылку кто-нить на статьи, а то какт-о фейком попахивает

ПС: Я тоже за равенство P и NP, хотя вся компьютерная техника, программы и информатика построена на противоположном. И чтобы это подтвердить и получить какието результаты нужно много чего менять

Гордость, за Русского человека!

А ссылкой на доказательство может поделитесь?:) Я бы тоже с интересом почитал на чем оно основано)

BelBES в смысле ссылкой? Могу сказать что это есть в стандартной учебной программе , причём в явном виде ещё до третьего класса.
Например одна секунда не равна жизни всей вселенной. Однако если есть точные инструкции для уничтожения всей вселенной за одну секунду -то равенство равно.
Объектом для операций может быть что угодно .
Есно самое вкусное это золото и свинец. Именно для этой парочки и придумали такую хитрожопую формулу. Но в этой вселенной ничего не бывает бесплатно - халявы не будет.

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

Как пример: Пусть у нас есть булевская функция от 100 параметров, нужно найти такой набор параметров, при котором функция будет возвращать 1. Проверить решение можно за линейное время(тупо подставить его и вычислить значение функции), а вот чтобы найти такой набор, нужно перебирать 2^100 различных вариантов решения, что очень много. И тут возникает мысль, а может существует алгоритм поиска решения, который будет не сложнее алгоритма проверки этого решения...вполне разумная гипотеза кстати.

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

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

Это сообщение отредактировал BelBES - 14.12.2013 - 18:12

Если я ничего не путаю, то это значит что задачу можно решить быстрее, чем за экспоненциальное время (т.е. не полным перебором). А из этого следует одна большая жопа - все криптографические алгоритмы основанные на том принципе, что их нельзя решить быстрее чем за еxp. время будут дефакто "обезоружены" и перестанут быть надёжными. Теперь все будут искать способы взлома. Печалька.

Не факт что печалька. Там вполне может быть полином, который становится меньше экспоненты только при каких-то безумных значениях n.
Да и что-то у меня есть сомнение, что первое же доказательство этого факта будет конструктивным... Скорее там будут какие-то совершенно адские доказательства того, что существует алгоритм решения некоторой NP-полной задачи. При этом, вполне вероятно, ещё и без приведения этого самого алгоритма.


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

Я и не говорил, что хэш однозначен. Ну а что мешает раздавать не только хэш, но и некоторую выборку кусков файла, которые вкупе будут однозначно определять исходник? Проверка соответствия файла хэшу = проверка решения. Если P = NP, то поиск этого решения не сложнее проверки. Не вопрос, если возможных вариантов более одного. дополнительная проверка даст правильный результат. Полагаю, что достаточно будет проверить даже соответствие заголовка файла. Если это видео, что можно понять по расширению файла, то первые байты будут описывать содержимое: кодеки, битрейт, контейнер. Если и этого недостаточно, то надергай с пару десятков байт из разных мест файла и сравни результаты, чтобы отсеять неправильные.

Добавлено в 20:03

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

Надеюсь деньги к нему попадут, а не осядут у чинуш ... молодец мужик!!! Голова варит! Это 5+

Как то все углубились над рассуждениями о наличие или отсутствии данной проблемы, а меня вообще смущает тот факт, что такого журнала "Автоматика и механика" выпускаемого академией наук не существует.
Да и вообще, если ученый доказал что-то великое, наверное он попытается это опубликовать в каких-то более высокорейтинговых журналах.
Так что по моему мнению фейк!