BelBES в смысле ссылкой? Могу сказать что это есть в стандартной учебной программе , причём в явном виде ещё до третьего класса. Например одна секунда не равна жизни всей вселенной. Однако если есть точные инструкции для уничтожения всей вселенной за одну секунду -то равенство равно. Объектом для операций может быть что угодно . Есно самое вкусное это золото и свинец. Именно для этой парочки и придумали такую хитрожопую формулу. Но в этой вселенной ничего не бывает бесплатно - халявы не будет.
Ссылкой на доказательство гипотезы, по которому вы сделали вывод, что это фуфел... И о какой вы там учебной программе говорите непонятно, если это в курсе студентов кибернетиков теория сложности алгоритмов далеко не на первом курсе изучается... И да, вы похоже не поняли суть проблемы. А она состоит в следующем, есть множество задач, решение которых фактически сводится к полному перебору, но при этом проверить это решение можно за полиномиальной время. И суть задачи состоит в том, чтобы доказать или опровергнуть, что если решение можно проверить за полиномиальное время, то и найти его можно тоже за полиномиальное время.
Как пример: Пусть у нас есть булевская функция от 100 параметров, нужно найти такой набор параметров, при котором функция будет возвращать 1. Проверить решение можно за линейное время(тупо подставить его и вычислить значение функции), а вот чтобы найти такой набор, нужно перебирать 2^100 различных вариантов решения, что очень много. И тут возникает мысль, а может существует алгоритм поиска решения, который будет не сложнее алгоритма проверки этого решения...вполне разумная гипотеза кстати.
Ну и для полного понимания, что этот вопрос вполне актуален: для многих NP задач существуют варианты решения за разумное время, которые основываются на некоторых эвристиках и не гарантирующие, что решение будет найденно. Например, подбор пароля по его хэшу, там обычно используют радужные таблицы(таблицы с кучей заранее просчитанных хэшей для разных паролей) и там задача сводится к простому поиску соответствия в таблице для заданного хэша, но при этом его может и не быть в таблице...
з.ы. ну и да, не надо слишком упрощать математические абстракции до уровня "понятного первокласснику", т.к. там нередко суть кроется в деталях которые упускаются при упрощении...
При подборе пароля по хэшу обычно считается прямая функция, а не обратная. Кроме тех случаев, когда сама функция неудачна. То есть по сути уже доказано, что N <> NP, но пока только на конкретных примерах. Нет только универсального математического определения этого. Поэтому новость о том что они равны автоматически фейк )
Добавлено в 21:07 брр... ну в смысле p <> np, у прикладников-программистов это просто не так называется )
Весьма интересно, выше линк уже давали - это не так давно доказал другой, профессор, причем он из Украины, преподавал у меня. Так что не надо тут ля-ля, второй тупо спер
BelBES в смысле ссылкой? Могу сказать что это есть в стандартной учебной программе , причём в явном виде ещё до третьего класса. Например одна секунда не равна жизни всей вселенной. Однако если есть точные инструкции для уничтожения всей вселенной за одну секунду -то равенство равно. Объектом для операций может быть что угодно . Есно самое вкусное это золото и свинец. Именно для этой парочки и придумали такую хитрожопую формулу. Но в этой вселенной ничего не бывает бесплатно - халявы не будет.
Ссылкой на доказательство гипотезы, по которому вы сделали вывод, что это фуфел... И о какой вы там учебной программе говорите непонятно, если это в курсе студентов кибернетиков теория сложности алгоритмов далеко не на первом курсе изучается... И да, вы похоже не поняли суть проблемы. А она состоит в следующем, есть множество задач, решение которых фактически сводится к полному перебору, но при этом проверить это решение можно за полиномиальной время. И суть задачи состоит в том, чтобы доказать или опровергнуть, что если решение можно проверить за полиномиальное время, то и найти его можно тоже за полиномиальное время.
Как пример: Пусть у нас есть булевская функция от 100 параметров, нужно найти такой набор параметров, при котором функция будет возвращать 1. Проверить решение можно за линейное время(тупо подставить его и вычислить значение функции), а вот чтобы найти такой набор, нужно перебирать 2^100 различных вариантов решения, что очень много. И тут возникает мысль, а может существует алгоритм поиска решения, который будет не сложнее алгоритма проверки этого решения...вполне разумная гипотеза кстати.
Ну и для полного понимания, что этот вопрос вполне актуален: для многих NP задач существуют варианты решения за разумное время, которые основываются на некоторых эвристиках и не гарантирующие, что решение будет найденно. Например, подбор пароля по его хэшу, там обычно используют радужные таблицы(таблицы с кучей заранее просчитанных хэшей для разных паролей) и там задача сводится к простому поиску соответствия в таблице для заданного хэша, но при этом его может и не быть в таблице...
з.ы. ну и да, не надо слишком упрощать математические абстракции до уровня "понятного первокласснику", т.к. там нередко суть кроется в деталях которые упускаются при упрощении...
При подборе пароля по хэшу обычно считается прямая функция, а не обратная. Кроме тех случаев, когда сама функция неудачна. То есть по сути уже доказано, что N <> NP, но пока только на конкретных примерах. Нет только универсального математического определения этого. Поэтому новость о том что они равны автоматически фейк )
Добавлено в 21:07 брр... ну в смысле p <> np, у прикладников-программистов это просто не так называется )
На каком например примере это доказано? з.ы. криптографическая хэш функция по определению не должна иметь обратной функции, но на данный момент не существует ни одной такой функции, для которой необратимость была-бы доказана...
Если доказательство челябинского ученого окажется верным, то это сильно повлияет на развитие математики, экономики и технических наук. Оптимизационные задачи в бизнесе будут решаться точнее, отсюда будет больше прибыли и меньше издержек у компании
То есть математик дал эксплуататорам в руки ещё один инструмент для угнетения эксплуатируемого класса.
Почти них... не понял, но могу предположить, что все остальные забили на решение т.к. метод перебора 30 лет назад (на арифмометре) и метод перебора сейчас (на гигагерцах) сделали проблему неактуальной.
Почти них... не понял, но могу предположить, что все остальные забили на решение т.к. метод перебора 30 лет назад (на арифмометре) и метод перебора сейчас (на гигагерцах) сделали проблему неактуальной.
Не забили:) Проблема в том, что оценка времени перебора для некоторых задач сравнима с возрастом вселенной, там никакие гигагерцы не спасут:)
BelBES Любая функция обратима за единицу времени , если известна её последовательность выполнения, причём прямое выполнение функции тоже занимает ту самую единицу времени. Неизвестная последовательность выполнения операций над объектом тоже занимает единицу времени , другая проблема что вариантов перебора получается многовато (точнее бесконечность). Когда будет доказано что бесконечное время равно измеряемому промежутку времени - тогда и поговорим.
И я думаю что лучше не использовать термины из высшей математики , не у всех есть корочки.
BelBES в смысле ссылкой? Могу сказать что это есть в стандартной учебной программе , причём в явном виде ещё до третьего класса. Например одна секунда не равна жизни всей вселенной. Однако если есть точные инструкции для уничтожения всей вселенной за одну секунду -то равенство равно. Объектом для операций может быть что угодно . Есно самое вкусное это золото и свинец. Именно для этой парочки и придумали такую хитрожопую формулу. Но в этой вселенной ничего не бывает бесплатно - халявы не будет.
Ссылкой на доказательство гипотезы, по которому вы сделали вывод, что это фуфел... И о какой вы там учебной программе говорите непонятно, если это в курсе студентов кибернетиков теория сложности алгоритмов далеко не на первом курсе изучается... И да, вы похоже не поняли суть проблемы. А она состоит в следующем, есть множество задач, решение которых фактически сводится к полному перебору, но при этом проверить это решение можно за полиномиальной время. И суть задачи состоит в том, чтобы доказать или опровергнуть, что если решение можно проверить за полиномиальное время, то и найти его можно тоже за полиномиальное время.
Как пример: Пусть у нас есть булевская функция от 100 параметров, нужно найти такой набор параметров, при котором функция будет возвращать 1. Проверить решение можно за линейное время(тупо подставить его и вычислить значение функции), а вот чтобы найти такой набор, нужно перебирать 2^100 различных вариантов решения, что очень много. И тут возникает мысль, а может существует алгоритм поиска решения, который будет не сложнее алгоритма проверки этого решения...вполне разумная гипотеза кстати.
Ну и для полного понимания, что этот вопрос вполне актуален: для многих NP задач существуют варианты решения за разумное время, которые основываются на некоторых эвристиках и не гарантирующие, что решение будет найденно. Например, подбор пароля по его хэшу, там обычно используют радужные таблицы(таблицы с кучей заранее просчитанных хэшей для разных паролей) и там задача сводится к простому поиску соответствия в таблице для заданного хэша, но при этом его может и не быть в таблице...
з.ы. ну и да, не надо слишком упрощать математические абстракции до уровня "понятного первокласснику", т.к. там нередко суть кроется в деталях которые упускаются при упрощении...
При подборе пароля по хэшу обычно считается прямая функция, а не обратная. Кроме тех случаев, когда сама функция неудачна. То есть по сути уже доказано, что N <> NP, но пока только на конкретных примерах. Нет только универсального математического определения этого. Поэтому новость о том что они равны автоматически фейк )
Добавлено в 21:07 брр... ну в смысле p <> np, у прикладников-программистов это просто не так называется )
На каком например примере это доказано? з.ы. криптографическая хэш функция по определению не должна иметь обратной функции, но на данный момент не существует ни одной такой функции, для которой необратимость была-бы доказана...
Не совсем так. Она должна по обратной функции иметь достаточно много корней, чтобы пользоваться ей было бессмысленно. Ну не быстрей, чем обычным брутом. И по конкретным доказывать вроде как нечего, формула-то одна и та же, считай хоть прямо, хоть обратно.
BelBES Любая функция обратима за единицу времени , если известна её последовательность выполнения, причём прямое выполнение функции тоже занимает ту самую единицу времени. Неизвестная последовательность выполнения операций над объектом тоже занимает единицу времени , другая проблема что вариантов перебора получается многовато (точнее бесконечность). Когда будет доказано что бесконечное время равно измеряемому промежутку времени - тогда и поговорим.
И я думаю что лучше не использовать термины из высшей математики , не у всех есть корочки.
Собственно любое отображение с потерей информации - необратимо. И это относится не только к хэш-функциям, но и например к проецированию 3D пространства на 2D плоскость, где по проекции в общем случае нельзя восстановить искомое пространство.
BelBES в смысле ссылкой? Могу сказать что это есть в стандартной учебной программе , причём в явном виде ещё до третьего класса. Например одна секунда не равна жизни всей вселенной. Однако если есть точные инструкции для уничтожения всей вселенной за одну секунду -то равенство равно. Объектом для операций может быть что угодно . Есно самое вкусное это золото и свинец. Именно для этой парочки и придумали такую хитрожопую формулу. Но в этой вселенной ничего не бывает бесплатно - халявы не будет.
Ссылкой на доказательство гипотезы, по которому вы сделали вывод, что это фуфел... И о какой вы там учебной программе говорите непонятно, если это в курсе студентов кибернетиков теория сложности алгоритмов далеко не на первом курсе изучается... И да, вы похоже не поняли суть проблемы. А она состоит в следующем, есть множество задач, решение которых фактически сводится к полному перебору, но при этом проверить это решение можно за полиномиальной время. И суть задачи состоит в том, чтобы доказать или опровергнуть, что если решение можно проверить за полиномиальное время, то и найти его можно тоже за полиномиальное время.
Как пример: Пусть у нас есть булевская функция от 100 параметров, нужно найти такой набор параметров, при котором функция будет возвращать 1. Проверить решение можно за линейное время(тупо подставить его и вычислить значение функции), а вот чтобы найти такой набор, нужно перебирать 2^100 различных вариантов решения, что очень много. И тут возникает мысль, а может существует алгоритм поиска решения, который будет не сложнее алгоритма проверки этого решения...вполне разумная гипотеза кстати.
Ну и для полного понимания, что этот вопрос вполне актуален: для многих NP задач существуют варианты решения за разумное время, которые основываются на некоторых эвристиках и не гарантирующие, что решение будет найденно. Например, подбор пароля по его хэшу, там обычно используют радужные таблицы(таблицы с кучей заранее просчитанных хэшей для разных паролей) и там задача сводится к простому поиску соответствия в таблице для заданного хэша, но при этом его может и не быть в таблице...
з.ы. ну и да, не надо слишком упрощать математические абстракции до уровня "понятного первокласснику", т.к. там нередко суть кроется в деталях которые упускаются при упрощении...
При подборе пароля по хэшу обычно считается прямая функция, а не обратная. Кроме тех случаев, когда сама функция неудачна. То есть по сути уже доказано, что N <> NP, но пока только на конкретных примерах. Нет только универсального математического определения этого. Поэтому новость о том что они равны автоматически фейк )
Добавлено в 21:07 брр... ну в смысле p <> np, у прикладников-программистов это просто не так называется )
На каком например примере это доказано? з.ы. криптографическая хэш функция по определению не должна иметь обратной функции, но на данный момент не существует ни одной такой функции, для которой необратимость была-бы доказана...
Не совсем так. Она должна по обратной функции иметь достаточно много корней, чтобы пользоваться ей было бессмысленно. Ну не быстрей, чем обычным брутом. И по конкретным доказывать вроде как нечего, формула-то одна и та же, считай хоть прямо, хоть обратно.
Прелесть хэш-функции, с точки зрения взломщика в том, что достаточно найти любую коллизию для данного хеша, и она будет валидной, даже если не будет совпадать с настоящим паролем
Если количество корней при обратном расчете будет тупо равно бруту, это ровным счетом ничего не меняет в стойкости пароля - количество итераций-то то же.
Добавлено в 01:23 Но вообще-то их будет больше, хотя бы потому что при обратном расчете получатся в том числе и такие символы, которых и на клавиатуре-то нет, и при прямом подборе их рассматривать не имеет смысла. :)
Если количество корней при обратном расчете будет тупо равно бруту, это ровным счетом ничего не меняет в стойкости пароля - количество итераций-то то же.
Какая разница сколько там корней, если при подсовывании криптосистеме в качестве пароля любого из них, та его с радостью проглотит как правильный?
BelBES Не надо путать понятия , одно дело выполнять точные инструкции и совсем другое дело -терять информацию. К слову при проецировании света от трёхмерного объекта на плоскость - всегда получается интерполяционная структура рисунка , с лазером это заметно на глаз. Ну а в нашем случае в условии задачи будут известны вектор и фаза для каждого фотона !! - это и есть полное обратное выполнение операций над объектом. И не надо упрощать условия задачи. Математика этого не прощает.
Без известных вектора и фазы для каждого фотона упавших на фотопластинку - восстановление трёхмерного изображения объекта (до совпадения 100%) - займёт бесконечное время.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста, или зарегистрируйтесь, если не зарегистрированы.
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
Им то может и надо, а вот нахуя я это всё прочитал? 
yaplakal.com
Heckfy22314 дек 2013 в 20:12